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())
L = []
for i in range(N):
  Ls = list(map(int, input().split()))
  Ls.pop(0)
  Ls = [l-1 for l in Ls]
  L.append(Ls)
#print(L)
UF = list(range(N+M))
def par(m):
  s = []
  r = UF[m]
  while r != m:
    s.append(m)
    m = r
    r = UF[m]
  for i in s:
    UF[i] = r
  return r
def unite(m, n):
  i = par(m)
  j = par(n)
  UF[j] = i
for i in range(N):
  Ls = L[i]
  for l in Ls:
    unite(i, N+l)
    unite(N+l, i)
#print(UF)
#for i in range(N+M):
#  p = par(i)
#print(UF)
ok = True
for i in range(1, N):
  if par(i) != par(i-1):
    ok = False
    break
if ok:
  print("YES")
else:
  print("NO")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
L = {}
for i in range(N):
    A = list(map(int, input().split()))
    for j, a in enumerate(A):
        if j == 0:
            continue
        if not a-1 in L.keys():
            L[a-1] = [i]
        else:
            L[a-1].append(i)

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)]

union = UnionFind(N)

for list_l in L.values():
    for l in list_l:
        union.Unite(l, list_l[0])

ans = "YES"
for i in range(N):
    if not union.isSameGroup(0, i):
        ans = "NO"
print(ans)

Submission status: Accepted

Solution code:
#C問題
#UnionFind(normal)
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)]

    
"""
実装例
ABC126E 1or2

#E問題
#UnionFind(normal) 
UFコードは省略
    
if __name__ == "__main__":
  
    N,M = map(int,input().split())
    uf = UnionFind(N+1)
    for i in range(M):
        X,Y,Z = map(int,input().split())
        if not uf.isSameGroup(X,Y):
            uf.Unite(X,Y)
    ans=0
    for j in uf.root[1:N+1]:
        if j < 0:
            ans+=1
    print(ans)
"""


N,M = map(int,input().split())
edges = []

for i in range(N):
    Linput = list(map(int,input().split()))
    k = Linput[0]
    for j in range(k):
        L = Linput[j+1]+N-1
        edges.append([i,L])
        
uf = UnionFind(N+M)
for edge in edges:
    x,y = edge[0],edge[1]
    if not uf.isSameGroup(x,y):
        uf.Unite(x,y)
        
flag = 0
for i in range(N-1):
    I = i+1
    if not uf.isSameGroup(0,I):
        flag = 1
        break
        
print("YES" if flag == 0 else "NO")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#CODEFESTIVAL2016Final C

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def union(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()
par = [i for i in range(n)]
rank = [0]*n
language = [[] for _ in range(m)]
for i in range(n):
    a = LI()
    k = a[0]
    for j in range(1,k+1):
        language[a[j]-1].append(i)
for i in range(m):
    l = len(language[i])
    for j in range(l-1):
        if root(language[i][j]) != root(language[i][j+1]):
                union(language[i][j],language[i][j+1])
for i in range(m)[::-1]:
    l = len(language[i])
    for j in range(l-1):
        if root(language[i][j]) != root(language[i][j+1]):
            union(language[i][j],language[i][j+1])
for i in range(n-1):
    if par[i] != par[i+1]:
        print('NO')
        quit()
print('YES')

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.ps = [-1]*(n+1)
    def find(self,x):
        if self.ps[x]<0:
            return x
        else:
            self.ps[x]=self.find(self.ps[x])
            return self.ps[x]
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return False
        if self.ps[x]>self.ps[y]:
            x,y = y,x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True
    def same(self,x,y):
        return self.find(x)==self.find(y)
    def size(self,x):
        x = self.find(x)
        return -self.ps[x]

n,m = map(int, input().split())
uf = UnionFind(n+m)
for i in range(1,n+1):
  l = list(map(int, input().split()))
  for j in range(1,1+l[0]):
    uf.unite(i,n+l[j])
for i in range(n+1,n+m+1):
  if uf.size(i) == 1:
    uf.unite(1,i)
print("YES" if uf.size(1) == n+m else "NO")

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

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

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            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 False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

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

#%%
N,M = [int(x) for x in input().split()]
people = [[i+M+1]+[int(x) for x in input().split()]for i in range(N)]
#%%
un = UnionFind(N+M+1)
for p in people:
    num=p[0]
    L=p[2:]
    for l in L:
        un.unite(num,l)
for i in range(M+2,M+N+1):
    if(not un.same(M+1,i)):
        print('NO')
        break
else:
    print('YES')

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(n+m)
s=set()
for i in range(n):
    l=list(map(int,input().split()))
    for j in l[1:]:
        UF.Unite(i,n+j-1)
        s.add(j)
print("YES" if UF.Count(0)-len(s)==n else "NO")

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
edge = [[]for i in range(N+M)]
for i in range(N):
    l = list(map(int,input().split()))[1:]
    for j in l:
        edge[i].append(N+j-1)
        edge[N+j-1].append(i)
A = [0]*(N+M)
A[0] = 1
queue = deque([0])
while queue != deque([]):
    p = queue.popleft()
    for i in edge[p]:
        if A[i] == 0:
            A[i] = 1
            queue.append(i)
if sum(A[:N]) == N:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
L=[list(map(int,input().split())) for i in range(N)]
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(M)
used=[0]*M
for x,*l in L:
    used[l[0]-1]=1
    for i in range(x-1):
        used[l[i+1]-1]=1
        u.unite(l[i]-1,l[i+1]-1)
print(['NO','YES'][u.size(L[0][1]-1)==sum(used)])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p_list=[list(map(lambda x:int(x)-1,input().split()))[1:] for _ in [0]*n]

p_check=[False for _ in [0]*n]
l_check=[False for _ in [0]*m]
l_list=[[] for _ in [0]*m]

for k,i in enumerate(p_list):
    for j in i:
        l_list[j].append(k)

for i,j in enumerate(l_list):
    if j!=[]:
        q=[i]
        break

l_check[q[0]]=True

while q:
    qq=q.pop()
    p=l_list[qq]
    for pp in p:
        if p_check[pp]==False:
            p_check[pp]=True
            for l in p_list[pp]:
                if l_check[l]==False:
                    l_check[l]=True
                    q.append(l)

print(["NO","YES"][all(p_check)])

Submission status: Accepted

Solution code:
#二部グラフで連結判定
N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N]

E = [[] for _ in [0]*(N+M)] #E[0] - E[N-1]:人, E[N] - E[N+M-1]:言語
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[i].append(N+l-1)
        E[N+l-1].append(i)

def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

d = dist_bfs(N+M,E,0)
ans = d[:N].count(-1)==0
print("YES" if ans else "NO")

Submission status: Accepted

Solution code:
#二部グラフで連結判定
N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N]

E = [[] for _ in [0]*(N+M)] #E[0] - E[N-1]:人, E[N] - E[N+M-1]:言語
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[i].append(N+l-1)
        E[N+l-1].append(i)

def connect_bfs(N,E,start):
    connect = {start}
    q = [start]
    while q:
        i = q.pop()
        for j in E[i]:
            if j in connect:continue
            connect.add(j)
            q.append(j)
    return connect

c = connect_bfs(N+M,E,0)
ans = len(c & set(range(N)))==N
print("YES" if ans else "NO")

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N]

E = [{} for _ in [0]*(N+M)]
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[i][N+l-1] = 1
        E[N+l-1][i] = 1

def Dijkstra(N,E,start):
    d = [-1]*N
    q = [(0,start)]
    while q:
        ci,i = heapq.heappop(q)
        if d[i]!= -1:continue
        d[i] = ci
        for j,cj in E[i].items():
            if d[j]!=-1:continue
            heapq.heappush(q,(ci+cj,j))
    return d

d = Dijkstra(N+M,E,0)
ans = d[:N].count(-1)==0
print("YES" if ans else "NO")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N]

E = [[] for _ in [0]*(N+M)]
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[i].append(N+l-1)
        E[N+l-1].append(i)

def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        i = q.pop()
        di = d[i]
        for j in E[i]:
            if d[j]!=-1:continue
            d[j] = di+1
            q.append(j)
    return d

d = dist_bfs(N+M,E,0)
ans = d[:N].count(-1)==0
print("YES" if ans else "NO")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N]

E = [[] for _ in [0]*(N+M)]
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[i].append(N+l-1)
        E[N+l-1].append(i)

start = 0
d = [-1]*(N+M) #d[0] - d[N-1]:人, d[N] - D[N+M-1]:言語
d[start] = 0
q = [start]
while q:
    i = q.pop()
    for j in E[i]:
        if d[j]!=-1:continue
        d[j] = d[i]+1
        q.append(j)

ans = True
for b in d[:N]:
    ans = ans and (b>=0)
print("YES" if ans else "NO")

Submission status: Accepted

Solution code:
#二部グラフで連結判定
N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N]

c = [False]*(N+M) #d[0] - d[N-1]:人, d[N] - D[N+M-1]:言語
E = [[] for _ in [0]*(N+M)]
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[i].append(N+l-1)
        E[N+l-1].append(i)

start = 0
q = [start]
c[start] = True
while q:
    i = q.pop()
    for j in E[i]:
        if c[j]:continue
        c[j] = True
        q.append(j)

ans = True
for b in c[:N]:
    ans = ans and b
print("YES" if ans else "NO")

Submission status: Accepted

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


class UnionFindTree():
    def __init__(self, N):
        self.N = N
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

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

    def groups(self):
        groups = {}
        for k in range(self.N):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, M = map(int, input().split())
    uft = UnionFindTree(N)
    speakers = [[] for _ in range(M)]
    for i in range(N):
        langs = list(map(int, input().split()))
        for l in langs[1:]:
            speakers[l-1].append(i)
    for i in range(M):
        for j in range(1, len(speakers[i])):
            uft.unite(speakers[i][j-1], speakers[i][j])
    if len(uft.groups()) == 1:
        print("YES")
    else:
        print("NO")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N ]

E = [[[] for _ in [0]*N] , [[] for _ in [0]*M]]
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[0][i].append(l-1)
        E[1][l-1].append(i)

Check = [[False]*N,[False]*M]
Check[0][0] = True
q = [[0,0]]
while q:
    cl,i = q.pop()
    for j in E[cl][i]:
        if Check[1-cl][j]:continue
        q.append([1-cl,j])
        Check[1-cl][j] = True

if sum(Check[0]) == N:
    print("YES")
else:
    print("NO")

Submission status: Accepted

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


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 size(self, x):
        return -self.root[self.find_root(x)]


N, M = map(int, input().split())
lang = [[] for _ in range(M+1)]
for i in range(N):
    lang_list = list(map(int, input().split()))
    for j in range(1, len(lang_list)):
        lang[lang_list[j]].append(i)

UF = UnionFind(N)
for speaker in lang:
    for i in range(1, len(speaker)):
        UF.unite(speaker[0], speaker[i])

if UF.size(0) == N:
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 異なる集合に属する場合のみ併合
        if x != y:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]


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

u = UnionFind(len(l))
for i in range(len(l)):
    for j in range(len(l[i])):
        u.unite(i,l[i][j])

for i in range(n):
    if not u.same(0,i):
        print('NO')
        exit()
print('YES')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range((n+m))]
for i in range(n):
    a=[int(i)-1 for i in input().split()][1:]
    for l in a:
        g[i].append(n+l)
        g[n+l].append(i)

par=[i for i in range(n+m)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
        
def connect(x,y):
    rx=root(x)
    ry=root(y)
    if rx!=ry:
        par[rx]=ry
    return

for i in range(n+m):
    for nb in g[i]:
        connect(i,nb)

p=par[0]
ans='YES'
for i in range(n):
    if par[i]!=p:
        ans='NO'

print(ans)

Submission status: Accepted

Solution code:
n, m = [int(item) for item in input().split()]
query = []
appeared = set()
for i in range(n):
    line = [int(item) for item in input().split()]
    appeared.update(line[1:])
    query.append(line[1:])
    
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1] * 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 same_check(self, x, y):
        return self.find(x) == self.find(y)

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

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

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

uf = UnionFind(m)
for q in query:
    if len(q) == 1:
        continue
    for item in q[1:]:
        if not uf.same_check(q[0]-1, item-1):
            uf.union(q[0]-1, item-1)
    
par = uf.find(appeared.pop() - 1)
for item in appeared:
    if uf.find(item - 1) != par:
        print("NO")
        exit()
print("YES")

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same_check(self, x, y):
        return self.find(x) == self.find(y)
ass = set()
N,K=map(int,input().split())
uni = UnionFind(K-1)
for _ in range(N):
    t = list(map(int,input().split()))
    ass.add(t[1]-1)
    if t[0] !=1:
        for k in t[2:]:
            uni.union(t[1]-1,k-1)
            ass.add(k-1)
            #print(t[1]-1,k-1)
p = set()
for i in ass:
    d = uni.find(i)
    p.add(d)
print("YES" if 1 ==len(p) else "NO")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = [i for i in range(M)]
Y = [0] * M
def par(i):
    if X[i] == i:
        return i
    t = par(X[i])
    X[i] = t
    return t
c = 0
for _ in range(N):
    Z = [int(a) - 1 for a in input().split()][1:]
    i = Z[0]
    for j in Z:
        if Y[j] == 0:
            c += 1
            Y[j] = 1
        pi = par(i)
        pj = par(j)
        if pi != pj:
            X[pj] = pi
            c -= 1
if c == 1:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]
        # 負:=連結頂点数, 自身が根
        # 正:=親index, 0-indexed

    def is_root(self, x):
        return self.v[x] < 0

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

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

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

        if -self.v[x] < -self.v[y]:
            x, y = y, x
        # x を連結頂点数最大にする

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

    def get_size(self, x):
        x = self.find(x)
        return -self.v[x]


n, m = map(int, input().split())
e = []

uf = UnionFind(n + m)
for i in range(n):
    k, *l = map(int, input().split())
    l = tuple(map(lambda x: x - 1, l))
    e.append(l)

for i, lang_lst in enumerate(e):
    for lg in lang_lst:
        uf.merge(i, n + lg)

root = uf.find(0)
print('YES' if all(uf.find(i) == root for i in range(1, n)) else 'NO')

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
par,rank,ans = [i for i in range(m+n)],[0 for i in range(m+n)],"YES"
def root(x):
	if par[x]!=x: par[x] = root(par[x])
	return par[x]
def unite(x,y):
	x2,y2 = root(x),root(y)
	if x2!=y2:
		if rank[x2]<rank[y2]: par[x2] = y2
		else: par[y2] = x2
		if rank[x2]==rank[y2]: rank[x2]+=1
def same(x,y):
	return root(x)==root(y)
for i in range(n):
    y = [int(k)-1 for k in input().split()]
    for j in y[1:]: unite(j,m+i)
for i in range(1,n):
    if not same(m,m+i): ans = "NO"
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# Union-Find木
class UnionFind:
    def __init__(self, n):
        self.n = n
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)
        # あるノードを根とする集合に属するノード数
        self.size = [1] * (n+1)
        # あるノードを根とする集合が木かどうか
        self.tree = [True] * (n+1)

    # 根の検索(グループ番号と言えなくもない)
    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 union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)

        # 木かどうかの判定用
        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # あるノードの属する集合のノード数
    def get_size(self, x):
        return self.size[self.find(x)]

    # 木かどうかの判定
    def is_tree(self, x):
        return self.tree[self.find(x)]
    
    # 集合の数
    def len(self):
        res = set()
        for i in range(self.n+1):
            res.add(self.find(i))
        # グループ0の分を引いて返却
        return len(res) - 1


N,M=MAP()

# 言語毎の連結リストに各人を頂点として入れる
lang=[[] for i in range(M+1)]
for i in range(N):
    for j in LIST()[1:]:
        lang[j].append(i+1)

uf=UnionFind(N)
for i in range(1, M+1):
    for j in range(1, len(lang[i])):
        # 同じ言語で話せる人達を同じ集合に入れていく
        a,b=lang[i][j-1],lang[i][j]
        if not uf.same(a, b):
            uf.union(a, b)

# 最終的に全員が1つの集合に入っていればOK
if uf.len()==1:
    YES()
else:
    NO()