Problem:


Score : 400 points

Problem Statement

On a planet far, far away, M languages are spoken. They are conveniently numbered 1 through M.

For CODE FESTIVAL 20XX held on this planet, N participants gathered from all over the planet.

The i-th (1≦i≦N) participant can speak K_i languages numbered L_{i,1}, L_{i,2}, ..., L_{i,{}K_i}.

Two participants A and B can communicate with each other if and only if one of the following conditions is satisfied:

There exists a language that both A and B can speak.

There exists a participant X that both A and B can communicate with.

Determine whether all N participants can communicate with all other participants.

Constraints

2≦N≦10^5

1≦M≦10^5

1≦K_i≦M

(The sum of all K_i)≦10^5

1≦L_{i,j}≦M

L_{i,1}, L_{i,2}, ..., L_{i,{}K_i} are pairwise distinct.

Partial Score

200 points will be awarded for passing the test set satisfying the following: N≦1000, M≦1000 and (The sum of all K_i)≦1000.

Additional 200 points will be awarded for passing the test set without additional constraints.

Input

The input is given from Standard Input in the following format:

N M
K_1 L_{1,1} L_{1,2} ... L_{1,{}K_1}
K_2 L_{2,1} L_{2,2} ... L_{2,{}K_2}
:
K_N L_{N,1} L_{N,2} ... L_{N,{}K_N}

Output

If all N participants can communicate with all other participants, print YES. Otherwise, print NO.

Sample Input 1

4 6
3 1 2 3
2 4 2
2 4 6
1 6

Sample Output 1

YES

Any two participants can communicate with each other, as follows:

Participants 1 and 2: both can speak language 2.

Participants 2 and 3: both can speak language 4.

Participants 1 and 3: both can communicate with participant 2.

Participants 3 and 4: both can speak language 6.

Participants 2 and 4: both can communicate with participant 3.

Participants 1 and 4: both can communicate with participant 2.

Note that there can be languages spoken by no participant.

Sample Input 2

4 4
2 1 2
2 1 2
1 3
2 4 3

Sample Output 2

NO

For example, participants 1 and 3 cannot communicate with each other.



Sample input:
4 6
3 1 2 3
2 4 2
2 4 6
1 6


Sample output:
YES

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def ufinit(n):
  global ufsz, ufances
  ufsz = [1] * n
  ufances = [0] * n
  for i in range(n):
    ufances[i] = i

def ufroot(x):
  global ufances
  a = []
  y = x
  while ufances[y] != y:
    a.append(y)
    y = ufances[y]
  for z in a:
    ufances[z] = y
  return y

def ufconn(x,y):
  global ufsz, ufances
  i = ufroot(x)
  j = ufroot(y)
  if i==j:
    return
  #k  = [i,j].min
  k  = j if (ufsz[i]<ufsz[j]) else i
  if k==j:
    ufances[i] = j
  else:
    ufances[j] = i
  ufsz[k] = ufsz[i] + ufsz[j]

n,m = inm()
k = []
l = []
for i in range(n):
    z = inl()
    k.append(z[0])
    l.append(z[1:])
ufinit(n+m)
for i in range(n):
    for j in l[i]:
        ufconn(i,j+n-1)
r = ufroot(0)
for i in range(1,n):
    if ufroot(i)!=r:
        print('NO')
        exit()
print('YES')

Submission status: Accepted

Solution code:
class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return
N,M=map(int,input().split())
G=unionFind(M)
s=set()
for i in range(N):
  tmp=tuple(map(int,input().split()))
  s.add(tmp[1]-1)
  for x in tmp[2:]:
    G.unite(tmp[1],x)

parent=set()
for i in s:
  parent.add(G.root(i))

if len(parent)==1:
  print("YES")
else:
  print("NO")

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int,input().split())
edges_p = {}
edges_l = {}

for i in range(1,m+1):
    edges_l[i] = []

for i in range(1,n+1):
    tmp = list(map(int, input().split()))
    edges_p[i] = tmp[1:]
    for j in edges_p[i]:
        edges_l[j].append(i)


remains = set(range(1,n+1))
remains_l = set(range(1,m+1))
d = deque()

d.append(1)
remains.remove(1)

while(len(d) > 0):
    tmp = d.pop()
    for i in edges_p[tmp]:
        if i in remains_l:
            for j in edges_l[i]:
                if j in remains:
                    d.append(j)
                    remains.remove(j)
            remains_l.remove(i)

if(len(remains) == 0):
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from itertools import combinations

# Union Find
class UF(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        '''
        x が属するグループを探索
        '''
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        '''
        x と y のグループを結合
        '''
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        '''
        x と y が同じグループか否か
        '''
        return self.find(x) == self.find(y)

    def get_size(self, x):
        '''
        x が属するグループの要素数
        '''
        x = self.find(x)
        return self.size[x]

N,M = LI()
uf = UF(N+M)
for i in range(N):
    kl = LI()
    for l in kl[1:]:
        uf.union(i,N+l-1)

root = uf.find(0)
for i in range(1,N):
    now = uf.find(i)
    if now != root:
        print('NO')
        exit()
print('YES')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N,M = map(int,input().split())
    lang = [[] for _ in range(M)]
    for i in range(N):
        info = list(map(int,input().split()))
        info.pop(0)
        for num in info:
            lang[num-1].append(i)

    con = [[] for _ in range(N)]
    for s in lang:
        l = len(s)
        if l>1:
            for i in range(l-1):
                con[s[i]].append(s[i+1])
                con[s[i+1]].append(s[i])

    go = [False for _ in range(N)]
    go[0] = True
    que = deque([0])
    while que:
        now = que.pop()
        for fol in con[now]:
            if go[fol]:
                continue
            else:
                que.append(fol)
                go[fol] = True
                
    print("YES" if all(go) else "NO")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:


#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root

def main():
    N,M = MI()

    """
    全員が誰かと言語で話せて、それが連結ならOK
    """
    uf=UnionFind(N+M)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes

    for i in range(N):
        _,*L = MI_()
        for l in L:
            unite(l+N, i)
    
    r = get_root(0)
    for i in range(N):
        if r!=get_root(i):
            print("NO")
            return

    print("YES")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m=map(int,input().split())
tree = UnionFind(n+m+1) 
for i in range(n):
  l=list(map(int,input().split()))
  for j in range(1,len(l)):
    tree.unite(i,l[j]+n)
rt=tree.find(0)
# print(tree)
for i in range(1,n):
  # print(rt, tree.find(i))
  if rt!= tree.find(i):
    print("NO");exit()
print("YES")

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
G = {}
for i in range(1,N+1):
    L = list(map(int,input().split()))
    G[i] = [L[j]+10**5 for j in range(1,L[0]+1)]
    for j in range(1,L[0]+1):
        if L[j]+10**5 not in G:
            G[L[j]+10**5] = []
        G[L[j]+10**5].append(i)
hist = [0 for _ in range(2*10**5+1)]
hist[1] = 1
que = deque([1])
while que:
    x = que.popleft()
    for y in G[x]:
        if hist[y]==0:
            que.append(y)
            hist[y] = 1
flag = 1
for i in range(1,N+1):
    if hist[i]==0:
        flag = 0
        break
if flag==1:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict
INF = float("inf")


def yes():
    print("YES")  # type: str


def no():
    print("NO")  # type: str


class UnionFind(object):

    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def main():

    N, M = map(int, input().split())
    L = [0]*N
    lang_leader = defaultdict(int)
    for i in range(N):
        K, *L[i] = list(map(int, input().split()))
    # 前Nは人
    uf = UnionFind(N+1)
    for i in range(N):
        for l in L[i]:
            if lang_leader[l] == 0:
                lang_leader[l] = i+1
            else:
                uf.unite(i, lang_leader[l]-1)

    # print(uf.tree)
    # 人はすべて同じグループであるか
    flag = True
    for i in range(N):
        if not uf.same(0, i):
            flag = False
            break
    if flag:
        yes()
    else:
        no()

    pass


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
B = [list(map(int,input().split())) for i in range(n)]
max_m = -1
for i in range(n):
    for j in range(1, len(B[i])):
        max_m = max(max_m, B[i][j])

C = [[] for i in range(max_m + 1)]
for i in range(n):
    for j in range(1, len(B[i])):
        C[B[i][j]].append(i)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def size(self, x):
        if self.parents[x] < 0:
            return -self.parents[x]
        else:
            self.parents[x] = self.size(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def n_cc(self):  # 連結成分の数
        A = [i for i in self.parents if i < 0]
        return len(A)

U = UnionFind(n)
# print(C)

for i in range(len(C)):
    for j in range(len(C[i])-1):
        # print(i, j)
        U.union(C[i][j], C[i][j+1])

# print(U.parents)
# print(U.n_cc())
if U.n_cc() == 1:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    def root(self, A):
        if self.parent[A-1] < 0: #負の数-->その数は親
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) #負では無い時、親の場所が入っているから、親が属しているグループを、自分自身に入れる(一度確認したところは直接親を見れるようにする)
        return self.parent[A-1] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-1)）
        self.parent[B-1] = A #加えられた親の値を、加えた先の親の位置に書き変える
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False
            
# N, Q = map(int, input().split())
# uni = UnionFind(N)
# for _ in range(Q):
#     P, A, B = map(int, input().split())
#     if P == 1:
#         if uni.root(A) == uni.root(B): #親が同じかどうか
#             print ('Yes')
#         else:
#             print ('No')
#     else:
#         uni.connect(A, B)

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
L1 = []
L1_append = L1.append

uni = UnionFind(M + 1)
for _ in range(N):
    KL = list(map(int ,input().split()))
    tmp = KL[1]
    L1_append(tmp)
    for i in KL[2:]:
        uni.connect(tmp, i)

tmp = uni.root(L1[0])
for i in L1[1:]:
    if tmp != uni.root(i):
        print ('NO')
        exit()

print ('YES')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

#人は0からN-1,言語は1からMまで
N, M = rl()
KL = [rl() for _ in range(N)]
speak_lan = [[] for _ in range(M+1)] #0は使わない
for i, x in enumerate(KL):
    k, *lan = x
    for l in lan:
        speak_lan[l].append(i)

communicate = set()
used_language = set()
def dfs(person):
    global communicate
    global used_language
    lan = KL[person][1:]
    for l in lan:
        if l in used_language:
            continue
        used_language.add(l)
        for p in speak_lan[l]:
            if p not in communicate:
                communicate.add(p)
                dfs(p)

dfs(0)
if len(communicate) == N:
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
L = [list(map(int, input().split()))[1::] for _ in range(N)]

root = [i for i in range(M + 1)]
comp_size = [1] * (M + 1)

def root_find(x):
  y = root[x]
  if y == x:
    return x
  else:
    z = root_find(y)
    root[x] = z
    return z

def merge(x, y):
  rx = root_find(x)
  ry = root_find(y)
  sx = comp_size[x]
  sy = comp_size[y]
  if sx >= sy:
    root[ry] = rx
    comp_size[rx] = sx + sy
  else:
    root[rx] = ry
    comp_size[ry] = sx + sy

for l in L:
  for i in range(len(l) - 1):
    merge(l[i], l[i + 1])
#print("root:", root)

r = root_find(L[0][0])
for i in range(1, N):
  if r != root_find(L[i][0]):
    print("NO")
    exit()
#print("root:", root)
print("YES")

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
lang = [[] for i in range(m+1)]
graph = [[] for i in range(n+1)]
for i in range(n):
    for j in range(1,a[i][0]+1):
        lang[a[i][j]].append(i+1)
for i in range(m+1):
    if len(lang[i]) > 1:
        for j in range(len(lang[i])-1):
            graph[lang[i][j+1]].append(lang[i][j])
            graph[lang[i][j]].append(lang[i][j+1])
stack = [1]
visited = [0]*(n+1)
while stack:
    x = stack.pop()
    visited[x] = 1
    for y in graph[x]:
        if visited[y] == 1:
            continue
        stack.append(y)
if 0 not in visited[1:]:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
import sys

class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rank = [0] * (n + 1)

	def find(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return 0
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def isSame(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.root[self.find(x)]

def main():
	input = sys.stdin.buffer.readline
	n, m = map(int, input().split())
	lang = [[] for _ in range(m)]
	uf = UnionFind(n)
	for i in range(n):
		k, *ls = map(int, input().split())
		for l in ls:
			lang[l - 1].append(i)
	for speakers in lang:
		for x, y in zip(speakers, speakers[1:]):
			uf.unite(x, y)
	print("YES" if uf.size(0) == n else "NO")

if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m = map(int, input().split())
L = [[] for _ in range(m)]
for i in range(n):
  k, *l = map(int, input().split())
  for j in l:
    L[j-1].append(i)

uf = UnionFind(n)
for i in L:
  for j in range(len(i)-1):
    uf.union(i[j], i[j+1])
if uf.group_count() == 1:
  print("YES")
else:
  print("NO")

Submission status: Accepted

Solution code:
def examA():
    H, W = LI()
    S = [LSI() for _ in range(H)]
    Alpha = [chr(ord('A') + i) for i in range(26)]
    for i in range(H):
        for j in range(W):
            if S[i][j]=="snuke":
                ans = str(Alpha[j]) + str(i+1)
    print(ans)
    return

def examB():
    N = I()
    ans = []
    cur = int((N*2-1)**0.5)+1
    ansC = (cur+1)*cur//2
    neg = ansC-N
    if neg>cur:
        cur -=1
        ansC = (cur + 1) * cur // 2
        neg = ansC - N
    for i in range(1,cur+1):
        if i!=neg:
            ans.append(i)
    for v in ans:
        print(v)
#    print(cur,neg)
    return

def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    que = deque()
    que.append(e)
    len = [10**9]*n
    len[e] = 0
    while que:
        now = que.popleft()
        nowlen = len[now]
        for ne in fordfs[now]:
            if len[ne] == 10**9:
                len[ne] = nowlen+1
                que.append(ne)
    return len
def examC():
    N, M = LI()
    V = [[]for _ in range(N+M)]
    for i in range(N):
        L = LI()
        for k in range(1,L[0]+1):
            V[i].append(L[k]+N-1)
            V[L[k]+N-1].append(i)
    length = bfs(N+M,0,V)
    ans = "YES"
    for i in length[:N]:
        if i==10**9:
            ans = "NO"
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
K = []
L = []
for _ in range(N):
    k,*l = map(int,input().split())
    K.append(k)
    L.append(l)
    
graph = [[] for _ in range(N+M)]
for i in range(N):
    for l in L[i]:
        graph[i].append(N+l-1)
        graph[N+l-1].append(i)

visited = [0 for _ in range(N+M)]
visited[0] = 1
stack = [0]

while stack:
    node = stack.pop()
    for adj in graph[node]:
        if not visited[adj]:
            visited[adj] = 1
            stack.append(adj)
            
print('YES' if all(visited[:N]) else 'NO')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    # n,m の bipartite graph
    E=[[] for _ in range(n+m)]
    for i in range(n):
        L=list(map(lambda x:int(x)-1,input().split()))[::-1]
        L.pop()
        for l in L:
            E[i].append(n+l)
            E[n+l].append(i)

    # 0,...,n-1 が連結かどうかを見る
    used=[0]*(n+m)
    used[0]=1
    Q=[0]
    while(Q):
        v=Q.pop()
        for nv in E[v]:
            if(used[nv]): continue
            used[nv]=1
            Q.append(nv)

    print("YES" if(min(used[:n])==1) else "NO")
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

class UnionFind(object):
    def __init__(self,n):
        self.__par=list(range(n))
        self.__rank=[0]*n
        self.__size=[1]*n

    def root(self,k):
        if(self.__par[k]==k): return k
        self.__par[k]=self.root(self.__par[k])
        return self.__par[k]

    def unite(self,i,j):
        i=self.root(i); j=self.root(j)
        par=self.__par; rank=self.__rank; size=self.__size
        if(i==j): return False
        if(rank[i]>rank[j]):
            par[j]=i
            size[i]+=size[j]
        else:
            par[i]=j
            size[j]+=size[i]
            if(rank[i]==rank[j]): rank[j]+=1
        return True

    def is_same(self,i,j):
        return self.root(i)==self.root(j)

    def size(self,k):
        return self.__size[self.root(k)]

def resolve():
    n,m=map(int,input().split())
    uf=UnionFind(m)
    S=set()
    for _ in range(n):
        L=list(map(int,input().split()))[::-1]
        k=L.pop()
        for i in range(k):
            S.add(L[i]-1)
            if(i+1<k):
                uf.unite(L[i]-1,L[i+1]-1)

    print("YES" if(max(uf.size(i) for i in range(m))==len(S)) else "NO")
resolve()

Submission status: Accepted

Solution code:

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード

    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


N, M = map(int, input().split())

uf = UnionFind(M+1)
talker = [False]*(M+1)

for i in range(N):
    K, *L = map(int, input().split())
    f = -1
    for l in L:
        talker[l] = True
        if f == -1:
            f = l
        else:
            uf.Unite(f, l)

for m in range(M+1):
    if talker[m] is True:
        if not uf.isSameGroup(f, m):
            print('NO')
            exit()
print('YES')

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]
    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n,m = LI()
    N = n+m
    par = [i for i in range(N)]
    rank = [0]*N
    for i in range(n):
        l = LI()
        for j in l[1:]:
            unite(j-1,i+m)
    r = set([root(i) for i in range(m,N)])
    if len(r) == 1:
        print("YES")
    else:
        print("NO")
    return


#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
v = [[] for _ in range(N+M)]
for i in range(N) :
    K, *L = map(int, input().split())
    for l in L :
        v[N+l-1].append(i)
        v[i].append(N+l-1)

visited = [False] * (N + M)
visited[0] = True
q = [0]

while q :
    cur = q.pop()
    for nex in v[cur] :
        if not visited[nex] :
            q.append(nex)
            visited[nex] = True

if sum(visited[:N]) == N :
    print('YES')
else :
    print('NO')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, L):
    l2p = defaultdict(set)
    p2l = defaultdict(set)
    for i, l in enumerate(L):
        p2l[i+1] = set(l)
        for j in l:
            l2p[j].add(i+1)
    
    
    q = [1]
    p_done = set(q)
    l_done = set()
    while q:
        p = q.pop()
        for l in p2l[p]:
            if l in l_done:
                continue
            l_done.add(l)
            for p2 in l2p[l]:
                if p2 in p_done:
                    continue
                p_done.add(p2)
                q.append(p2)
    return 'YES' if set(range(1, N+1)) == p_done else 'NO'



def main():
    N, M = read_int_n()
    L = [read_int_n()[1:] for _ in range(N)]
    print(slv(N, M, L))


if __name__ == '__main__':
    main()