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 collections import deque
import sys
from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = y      #親の置き換え(圧縮)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        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 weighted_union(self, x, y, w):
        # print("unite",x,y,w,self.weight)
        px = self.find(x)
        py = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        # if px == py: return 0
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = - w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] =  w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0

    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)
input = sys.stdin.readline
n, m = map(int, input().split())
langs = [[] for i in range(m)]
for i in range(n):
    inputs = list(map(int, input().split()))
    k = inputs[0]
    ls = inputs[1:]
    for l in ls:
        langs[l-1].append(i)
# print(langs)
uf = UnionFind(n)
for l in langs:
    if len(l) <= 1: continue
    x = l[0]
    for y in l[1:]:
        if not uf.judge(x, y): uf.union(x, y)

ans = set()
for i in range(n):
    ans.add(uf.find(i))
if len(ans) == 1:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



class UnionFindTree:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.size = [1] * n

    def root(self, i):
        inter = set()
        while self.parent[i]!=i:
            inter.add(i)
            i = self.parent[i]
        r = i
        for i in inter:
            self.parent[i] = r
        return r

    def connect(self, i, j):
        if i==j:
            return
        ri = self.root(i)
        rj = self.root(j)
        if ri==rj:
            return
        if self.size[ri]<self.size[rj]:
            self.parent[ri] = rj
            self.size[rj] += self.size[ri]
        else:
            self.parent[rj] = ri
            self.size[ri] += self.size[rj]

n,m = map(int, input().split())
d = {i: [] for i in range(m)}
for i in range(n):
    l = list(map(lambda x: int(x)-1, input().split()))
    for j in l[1:]:
        d[j].append(i)
uf = UnionFindTree(n)
for item in d.values():
    if len(item)>=2:
        for u in item:
            uf.connect(item[0], u)
for i in range(n):
    uf.root(i)
if all(uf.parent[0] == item for item in uf.parent):
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)

n,m=map(int,input().split())

#n,m<=10**5

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 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()}

uf = UnionFind(m+1) #初期化

lastcheck=set([])
klkl=[]
for _ in range(n):
    kl=list(map(int,input().split()))[1:]
    if len(kl)>1:
        for item in kl[1:]:
            uf.union(kl[0]-1,item-1)
    klkl.append(kl)
uf_list=uf.members(klkl[0][0]-1)
#print(uf_list)
flag=0
for kl in klkl:
    for item in kl:
        item-=1
        if item not in uf_list:
            flag=1
        else:
            break
if flag==1:
    print("NO")
else:
    print("YES")

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]
KL = [[int(x) for x in input().split()] for _ in range(N)]


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


u = UnionFind(N + M)

for i, (kl) in enumerate(KL):
    for j, k in enumerate(kl):
        if j == 0:
            continue
        u.union(i, k + N - 1)

v = set()
for i in range(N):
    v.add(u.find(i))

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]

from collections import defaultdict
d = defaultdict(lambda: [])
for i,ls in enumerate(L):
    for l in ls[1:]:
        d[l].append(i)

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

uf = UnionFind(N)

for ls in d.values():
    for a,b in zip(ls,ls[1:]):
        if uf.is_same(a,b): continue
        uf.unite(a,b)

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n
    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

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

    def size(self,x):
        return self.tsize[self.root(x)]
      
n,m = tuple(map(int,input().split()))

ll = []
uf = UnionFind(m)
for _ in range(n):
  k, *l = tuple(map(int,input().split()))
  for i in range(k-1):
    uf.unite(l[i]-1,l[i+1]-1)
  ll.append(l[0]-1)

for lang in ll:
  if not uf.isSame(lang,ll[-1]):
    print("NO")
    exit()
print("YES")

Submission status: Accepted

Solution code:
from collections import deque
"""
https://tjkendev.github.io/procon-library/python/graph/bfs.html
"""
def bfs(G):
    dist = [-1]*(N+M)
    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)
    
    return dist

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

graph = [[] for _ in range(N+M)]

for i in range(N):
    KL = list(map(int,input().split()))
    for j in KL[1:]:
        graph[i].append(N+j-1)
        graph[N+j-1].append(i)

ans = bfs(graph)

if -1 in ans[:N]:
    print("NO")
else:
    print("YES")

Submission status: Accepted

Solution code:
def f():
    import sys
    input=sys.stdin.buffer.readline
    sys.setrecursionlimit(10**9)
    n,m=map(int,input().split())
    lang={}
    class UnionFind:
        #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
        #method -> foo.hoge(huga)
        __slots__ = ["_size", "_first_idx", "_parents"]
        def __init__(self, size: int, first_index: int = 0) -> None:
            self._size = size
            self._first_idx = first_index
            self._parents = [-1] * (size + first_index)
        def find(self, x: int) -> int:
            if self._parents[x] < 0:
                return x
            self._parents[x] = self.find(self._parents[x])
            return self._parents[x]
        def same(self, x: int, y: int) -> bool:
            return self.find(x) == self.find(y)
        def unite(self, x: int, y: int) -> bool:
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            if self._parents[x] > self._parents[y]:
                x, y = y, x
            self._parents[x] += self._parents[y]
            self._parents[y] = x
            return True
        def size(self, x: int) -> int:
            return -self._parents[self.find(x)]
        def group_count(self) ->int:
            return sum(1 for i in  self._parents if i<0)-self._first_idx
        def connected(self) ->bool:
            return self._parents[self.find(self._first_idx)]==-self._size
    uf=UnionFind(n)
    for i in range(n):
        k,*l=map(int,input().split())
        for j in l:
            if j in lang:
                uf.unite(i,lang[j])
            else:
                lang[j]=i
    print("YES")if uf.connected() else print("NO")





if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).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())
uf=UnionFind(m+1)
T=[]
for i in range(n):
  a=list(map(int,input().split()))
  k=a[0]
  for j in range(k-1):
    uf.union(a[j+1],a[j+2])
  T.append(a[1])
failflag=0
for i in range(n):
  if not uf.same(T[0],T[i]):
    failflag=1
if failflag==0:
  print('YES')
else:
  print('NO')

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    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()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = MAP()
L = [[x-1 for x in LIST()[1:]] for _ in range(N)]
uf = UnionFind(N)
graph = [[] for _ in range(M)]

for i, l in enumerate(L):
	for x in l:
		graph[x].append(i)

for i in range(M):
	if len(graph[i]) <= 1:
		continue
	p = graph[i][0]
	for x in graph[i][1:]:
		uf.union(p, x)

num_group = uf.group_count()
print("YES" if num_group == 1 else "NO")

Submission status: Accepted

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

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)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

#a = list(map(int, input().split()))
# list(map(int, input().split()))

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



#12-

n,m = list(map(int, input().split()))
u = UnionFind(n)

infos = []

humlng = [[] for i in range(m)]

for i in range(n):
    infos.append(list(map(int, input().split())))
    
    k = infos[-1]
    for j in range(1,len(k)):
        humlng[k[j]-1].append(i)

for i in humlng:
    if(len(i)<=1):
        continue
    for j in range(1,len(i)):
        u.union(i[0],i[j])
ans = True
for i in range(n):
    ans = ans and u.same_check(0,i)
    #print(ans)

print("YES" if ans else "NO")

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def union(self, 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.parent[y] = x
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int, input().split())
uf = UnionFind(N)
s = [set() for m in range(M+1)]
for i in range(N):
  KL = list(map(int, input().split()))
  for l in KL[1:]:
    s[l].add(i)

for m in range(1, M+1):
  if s[m]:
    u = s[m].pop()
    for v in s[m]:
      uf.union(u, v)

par = [uf.find(i) for i in range(N)]
if min(par) == max(par):
  print('YES')
else:
  print('NO')

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    ms = [[] for _ in [0]*(m+1)]
    ns = []
    for i in range(n):
        l = [int(i) for i in ipt().split()]
        ns.append(l[1::])
        for j in l[1::]:
            ms[j].append(i)
    q = queue.Queue()
    nal = [-1]*n
    mal = [-1]*(m+1)
    nal[0] = 1
    q.put((0,1))
    while not q.empty():
        qi1,qi2 = q.get()
        if qi2 == 1:
            for i in ns[qi1]:
                if mal[i] == -1:
                    mal[i] = 1
                    q.put((i,2))
        else:
            for i in ms[qi1]:
                if nal[i] == -1:
                    nal[i] = 1
                    q.put((i,1))
    if -1 in nal:
        print("NO")
    else:
        print("YES")

    return
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())

def main():
    n, m = map(int, input().split())
    uf = UnionFind(n)
    la = [None]*m
    for i in range(n):
        a = list(map(int, input().split()))
        for v in a[1:]:
            if la[v-1] is None:
                la[v-1] = i
            else:
                uf.union(i, la[v-1])
    if uf.group_count() == 1:
        print("YES")
    else:
        print("NO")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m),*t=[map(int,t.split())for t in open(0)]
*b,a=zip(*[(i,j+n,1)for i,(_,*t)in enumerate(t)for j in t])
print('YNEOS'[1in csgraph.connected_components(csr_matrix((a,b),[n-~m]*2))[1][:n]::2])

Submission status: Accepted

Solution code:
from scipy.sparse import*;(n,m),*d=[map(int,o.split())for o in open(0)];*w,a=zip(*[(i,j+n-1,1)for i,(_,*d)in enumerate(d)for j in d]);print("YNEOS"[1in csgraph.connected_components(csr_matrix((a,w),[n+m]*2))[1][:n]::2])

Submission status: Accepted

Solution code:
from scipy.sparse import*;(n,m),*d=[map(int,o.split())for o in open(0)];*w,a=zip(*[(i,j+n-1,1)for i,(_,*d)in enumerate(d)for j in d]);print("YNEOS"[1in csgraph.connected_components(csr_matrix(((a,w)),[n+m]*2))[1][:n]::2])

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m),*d=[map(int,o.split())for o in open(0)]
*w,a=zip(*[(i,j+n-1,1)for i,(_,*d)in enumerate(d)for j in d])
print("YNEOS"[1in csgraph.connected_components(csr_matrix(((a,w)),[n+m]*2))[1][:n]::2])

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m),*t=[map(int,t.split())for t in open(0)]
a,b,c=zip(*[(i,j+n-1,1)for i,(_,*t)in enumerate(t)for j in t])
print('YNEOS'[1in csgraph.connected_components(csr_matrix(((c,(a,b))),[n+m]*2))[1][:n]::2])

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m),*t=[map(int,t.split())for t in open(0)]
a,b,c=zip(*[(i,j+n-1,1)for i,(*t,)in enumerate(t)for j in t[1:]])
print('YNEOS'[1in csgraph.connected_components(csr_matrix(((c,(a,b))),[n+m]*2))[1][:n]::2])

Submission status: Accepted

Solution code:
from scipy.sparse import*
(n,m),*p=[map(int,t.split())for t in open(0)]
a,b,c=zip(*[(i,j+n-1,1)for i,q in enumerate(p)for j in list(q)[1:]])
print('YNEOS'[1in csgraph.connected_components(csr_matrix(((c,(a,b))),[n+m]*2))[1][:n]::2])

Submission status: Accepted

Solution code:
from numpy import*;from scipy.sparse import*;(n,m),*p=[map(int,o.split())for o in open(0)];e=array([(i,j+n-1,1)for i,q in enumerate(p)for j in list(q)[1:]]).T;print("YNEOS"[1in csgraph.connected_components(csr_matrix(((e[2],e[:2])),[n+m]*2))[1][:n]::2])

Submission status: Accepted

Solution code:
from numpy import*
from scipy.sparse import*
(n,m),*p=[map(int,o.split())for o in open(0)]
e=array([(i,j+n-1,1)for i,q in enumerate(p)for j in list(q)[1:]]).T
print("YNEOS"[1in csgraph.connected_components(csr_matrix(((e[2],e[:2])),[n+m]*2))[1][:n]::2])

Submission status: Accepted

Solution code:
from numpy import*
from scipy.sparse import*
(n,m),*p=[map(int,o.split())for o in open(0)]
e=array([(i,j+n-1,1)for i,q in enumerate(p)for j in list(q)[1:]]).T
print("NO"if 1 in csgraph.connected_components(csr_matrix(((e[2],e[:2])),[n+m]*2))[1][:n]else"YES")

Submission status: Accepted

Solution code:
#UnionFind木
class UnionFind():
    def __init__(self,N,M):
        self.N = N
        self.M = M
        self.parents = [-1]*(N + M)

    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,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):#xとyが同じグループにいるか判定
        return self.find(x) == self.find(y)
    
    def answer(self):
        r = self.find(0)
        if all(r == self.find(i) for i in range(1,self.N)):
            return True
        else:
            return False

N,M = map(int,input().split())
uf = UnionFind(N,M)
for i in range(N):
    A = list(map(int,input().split()))
    for a in A[1:]:
        uf.unite(i,a - 1 + N)
if uf.answer():
    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(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())
import sys
sys.setrecursionlimit(10**8)

def main():
    n,m = map(int,input().split())
    UF = UnionFind(n+m)
    for i in range(n):
        kl = list(map(int, input().split()))
        for j in range(1,len(kl)):
            UF.union(i,n+kl[j]-1)
    for i in range(n-1):
        if not UF.same(i,i+1):
            print('NO')
            return
    print('YES')
if __name__ == "__main__":
    main()