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:
n,m=map(int,input().split())
lang={i:[] for i in range(1,m+1)}
for _ in range(n):
    x=list(map(int,input().split()))
    K=x[0]
    for i in range(1,K+1):
        lan=x[i]
        lang[lan].append(_+1)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)
        
    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())



uni=UnionFind(n)
for i in range(1,m+1):
    lis=lang[i]
    if lis:
        x=lis[0]
        for i in range(1,len(lis)):
            uni.union(x,lis[i])
if uni.group_count()==2:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0] * n
        self.size = [1] * n

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

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

N, M = map(int, input().split())
uf = UnionFind(M+1)
Lf = [None]*N
for i in range(N):
    tmp = list(map(int, input().split()))
    K, L = tmp[0], tmp[1:]
    for j in range(K-1):
        uf.unite(L[j], L[j+1])
    Lf[i] = L[0]
r = uf.find(Lf[0])
for i in range(1, N):
    if r != uf.find(Lf[i]):
        print('NO')
        exit()
print('YES')

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
language={i:[] for i in range(1,M+1)}
for i in range(0,N):
    L=list(map(int,input().split()))
    K=L[0]
    for j in range(1,K+1):
        language[L[j]].append(i)

uf=UnionFindVerSize(N)
for i in range(1,M+1):
    if language[i]:
        p=language[i][0]
        if len(language[i])>1:
            for j in range(1,len(language[i])):
                uf.unite(p,language[i][j])


if uf.calc_group_num()==1:
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
#CODE FES 2016 C
n, m = map(int, input().split())

par=[i for i in range(n+m)]
size=[1 for _ in range(n+m)]
rank=[0 for _ in range(n+m)]
 
def find(x):#木の根を求める
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
    
def merge(x,y):#併合
    x=find(x)
    y=find(y)
    if x==y:
        return
    if rank[x]>rank[y]:
        par[y]=x
        size[x]+=size[y]
    else:
        par[x]=y
        size[y]+=size[x]
        if rank[x]==rank[y]:
            rank[y]+=1
            
def same(x,y):
    return find(x)==find(y)

for i in range(n):
    l = list(map(int, input().split()))[1:]
    for j in range(len(l)):
        merge(i, l[j]+n-1)
flg = True
for i in range(1, n):
    if not same(0, i):
        flg = False
print('YES' if flg else 'NO')

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)]
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
lan=[[] for _ in range(m)]
for i in range(n):
    l=list(map(int,input().split()))
    for j in range(1,l[0]+1):
        lan[l[j]-1].append(i)
h=UnionFind(n)
for i in range(m):
    if len(lan[i])>1:
        for j in range(1,len(lan[i])):
            h.Unite(lan[i][0],lan[i][j])
print("NO" if h.Count(0)-n else "YES")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, m = LI()
    par = [i for i in range(n)]
    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 y < x: x, y = y, x
        par[y] = x
        return
    ling = [[] for i in range(m)]
    for i in range(n):
        kl = LI()
        for l in kl[1:]:
            ling[l-1].append(i)
    for l in ling:
        if l:
            l0 = l[0]
            for li in l[1:]:
                unite(l0, li)
    for i in range(n):
        root(i)
    print("YES" if len(set(par)) == 1 else "NO")
    return


#main
if __name__ == '__main__':
    solve()

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())
import sys
input=sys.stdin.readline
n,m = map(int, input().split())
uf = UnionFind(m)
lang=set()
for i in range(n):
    lis = list(map(int,input().split()))
    for i in range(1,len(lis)-1):
        lang.add(lis[i]-1)
        uf.union(lis[i]-1,lis[i+1]-1)
    lang.add(lis[-1]-1)
e = next(iter(lang))
if lang == set(uf.members(e)):
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  def unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
      return
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
N,M = map(int, input().split())
u = UnionFind(N+M)
for i in range(N):
  inf = list(map(int, input().split()))
  for l in inf[1:]:
    u.unit(i,N+l-1)

ans = all(u.same(i,i+1) for i in range(N-1))
if ans:
  print('YES')
else:
  print('NO')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
g = [[] for _ in range(n)]
d = {}
for i in range(n):
    kl = list(map(int, input().split()))
    L = kl[1:]
    L = [l-1 for l in L]
    for l in L:
        if l not in d:
            d[l] = i
        else:
            g[d[l]].append(i)
            g[i].append(d[l])

from collections import deque
s = deque()
s.append(0)
visit = [-1]*n
visit[0] = 0
while s:
    x = s.pop()
    for nx in g[x]:
        if visit[nx] == -1:
            visit[nx] = 0
            s.append(nx)
if min(visit) != -1:
    print('YES')
else:
    print('NO')

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 same(self, x, y):
        return self.find(x) == self.find(y)


n, m = map(int, input().split())
uf = UnionFind(n + m)

for i in range(n):
    k, *L = map(int, input().split())
    for l in L:
        uf.union(l - 1, m + i)

for i in range(n - 1):
    if not uf.same(m + i, m + i + 1):
        print("NO")
        break
else:
    print("YES")

Submission status: Accepted

Solution code:
from collections import deque

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

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

visited = [False] * (N + M)
visited[0] = True
que = deque([0])
while que:
    v = que.popleft()

    for w in edge[v]:
        if visited[w]: continue
        visited[w] = True
        que.append(w)
    
flag = True
for i in range(N):
    if not visited[i]:
        flag = False

if flag:
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

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

tree = UnionFind(N + M)

for i in range(N):
    L = tuple(map(int, input().split()))
    for l in L[1:]:
        tree.union(i, N + l - 1)

V = set()
for i in range(N):
    V.add(tree.root(i))

print('YES' if len(V) == 1 else 'NO')

Submission status: Accepted

Solution code:
import sys;sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
    self.siz=n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
    self.siz-=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
  def size(self):
    return self.siz
n,m=map(int,input().split())
u=UnionFind(m+1)
ll=set()
for i in range(n):
  k,*l=map(int,input().split())
  if i==0:root=l[0]
  for j in range(len(l)-1):u.unite(l[j],l[j+1])
  ll|=set(l)
if len(ll)==u.count(root):print('YES')
else:print('NO')

Submission status: Accepted

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

    def get_root(self, i):
        while self.parent[i] != -1:
            i = self.parent[i]
        return i

    def is_same_tree(self, i, j):
        return self.get_root(i) == self.get_root(j)

    def merge(self, i, j):
        i = self.get_root(i)
        j = self.get_root(j)
        if i == j:
            return

        if self.rank[i] > self.rank[j]:
            self.parent[j] = i
            self.rank[i] = max(self.rank[i], self.rank[j] + 1)
        else:
            self.parent[i] = j
            self.rank[j] = max(self.rank[j], self.rank[i] + 1)

n, m = [int(i) for i in input().split()]
l = [[] for _ in range(m)]
for i in range(n):
    kl = [int(i)-1 for i in input().split()]
    for j in kl[1:]:
        l[j].append(i)
uf = UnionFind(n)
for i in l:
    for j in range(len(i) - 1):
        uf.merge(i[j], i[j + 1])

for i in range(n - 1):
    if not uf.is_same_tree(i, i + 1):
        print("NO")
        break
else:
    print("YES")

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    EdgeK = [[] for _ in range(M)]
    for i in range(N):
        L = [int(j) for j in input().split()]
        for j in L[1:]:
            Edge[i].append(j - 1)
            EdgeK[j - 1].append(i)

    Visited = [False] * N
    VK = [False] * M
    q = deque()
    q.append((0, 0)) #node, person (0) or lang (1)

    while q:
        nN, nT = q.pop()
        if nT == 0: #person
            if not Visited[nN]:
                Visited[nN] = True
                for ne in Edge[nN]:
                    if not VK[ne]: q.append((ne, 1))
        else:
            if not VK[nN]:
                VK[nN] = True
                for ne in EdgeK[nN]:
                    if not Visited[ne]: q.append((ne, 0))
    if False in Visited: print("NO")
    else: print("YES")


    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

from collections import defaultdict

G = defaultdict(list)

for i in range(n):
    ll = list(map(int, input().split()))[1:]
    for l in ll:
        G[l + n - 1].append(i)
        G[i].append(l + n - 1)
# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque

dist = [-1] * (n + m + 1)
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

if -1 in dist[:n]:
    print("NO")
else:
    print("YES")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = [1] * n
        self.group_num = n

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

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

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

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        self.group_num -= 1



n, m = LI()
lan = [[] for _ in range(m)]
uf = UnionFind(n)
for j in range(n):
    L = LI()
    k = L[0]
    for i in range(1, k + 1):
        lan[L[i] - 1] += [j]


for ll in lan:
    for s in range(len(ll)):
        uf.union(ll[s], ll[s - 1])

if uf.group_num == 1:
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

N, M = map(int, input().split())
L = [list(map(int, input().split()))[1:] for _ in range(N)]
uf = UnionFind(M+1)
used = [False] * (M+1)
for i in range(N):
    u = L[i][0]
    used[u] = True
    for v in L[i][1:]:
        used[v] = True
        uf.unite(u, v)
root = set()
for v in range(1, M+1):
    if used[v]:
        root.add(uf.find(v))
if len(root) == 1:
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

readline = sys.stdin.readline

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

a = []
b = []
for i in range(M + 1, M + N + 1):
    K, *L = map(int, readline().split())
    l = len(L)
    a.extend([i] * l)
    b.extend(L)

m = csr_matrix(([1] * len(a), (a, b)), shape=(N + M + 1, N + M + 1))
n, label = connected_components(m, directed=False)
if all(label[1 + M:] == label[1 + M]):
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
import numpy as np

readline = sys.stdin.readline

N, M = map(int, readline().split())
# 言語を頂点N+Kとする
a = []
b = []
for i in range(M + 1, M + N + 1):
    K, *L = map(int, readline().split())
    l = len(L)
    a.extend([i] * l)
    b.extend(L)

m = csr_matrix(([1] * len(a), (a, b)), shape=(N + M + 1, N + M + 1))
n, label = connected_components(m, directed=False)
if np.all(label[1 + M:] == label[1 + M]):
    print('YES')
else:
    print('NO')

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(list(self.roots()))

    def all_group_members(self):
        dic = {}
        for x in range(self.N):
            r = self.find(x)
            dic.setdefault(r, [])
            dic[r].append(x)
        return dic

import sys
input=sys.stdin.readline
def main():
    N,M=map(int, input().split())
    L=[list(map(int, input().split()))[1:]for _ in range(N)]
    UF=UnionFind(N+M)
    for i in range(N):
        for l in L[i]:
            UF.union(i,N+l-1)
    b=set(i for i in UF.members(0) if i < N)==set(range(N))
    print("YNEOS"[not b::2])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

# ユニオンファインド
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())
a= [list(map(int, input().split())) for i in range(n)]
uf=UnionFind(m)
x=[0]*m
for i in range(n):
    if a[i][0]==1:
        x[a[i][1]-1]=1
    else:
        for j in range(1,len(a[i])-1):
            uf.union(a[i][j]-1,a[i][j+1]-1)
            if x[a[i][j]-1]==0:
                x[a[i][j]-1]=1
            if j==len(a[i])-2:
                if x[a[i][j+1]-1]==0:
                    x[a[i][j+1]-1]=1

for i in range(m):
    if x[i]==0:
        if i==m-1:
            uf.union(m-1,0)
        else:
            uf.union(i,i+1)

y=uf.group_count()
if y==1:
    print('YES')

else:
    print('NO')

Submission status: Accepted

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    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):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        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
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]

uf = UnionFind(N+M)
for i in range(N):
    for j in range(1, L[i][0]+1):
        uf.unite(i+M+1, L[i][j])

ans = "YES"
for i in range(M+1, M+N+1):
    if uf.isSameGroup(M+1, i):
        continue
    ans = "NO"
    break

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

# pair[1,2,3,...,M] : 言語
# pair[M+1, M+2, ... M+N] : 人、こいつらが同じグラフ上にあればOK
pair = [-1] * (N + M + 1)

cnt = 1
for i in range(1, N + M + 1):
    if pair[-1] == -1:
        node = [i]
        pair[i] = cnt
        while node:
            s = node.pop()
            for t in edge[s]:
                if pair[t] == -1:
                    pair[t] = cnt
                    node.append(t)
        cnt += 1

tmp = pair[M + 1]
ans = "YES" if all(tmp == i for i in pair[M + 1:]) else "NO"
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
import copy
N,M=map(int,input().split())
KL=[list(map(int,input().split())) for i in range(N)]

human=[set() for i in range(N+1)]
gengo=[set() for i in range(M+1)]
for i in range(N):
    for m in range(1,KL[i][0]+1):
        human[i].add(KL[i][m])
        gengo[KL[i][m]].add(i)

usedhuman=set([1])
usedgengo=set(human[1])
stack=[i for i in human[1]]
while stack:
    g=stack.pop()
    for h in gengo[g]:
        if not h in usedhuman:
            usedhuman.add(h)
            for ng in human[h]:
                if not ng in usedgengo:
                    usedgengo.add(ng)
                    stack.append(ng)

if len(usedhuman)==N:
    print("YES")
else:
    print("NO")