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:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################
class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * 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 find(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
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
    
    def __str__(self):
        rt=[i if j<0 else j for i,j in enumerate(self.table)]
        return str(rt)


show_flg=False
show_flg=True

ans=0
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)

uf=UnionFind(n+m)

for i in range(n+m):
    for nb in g[i]:
        uf.union(i,nb)
p=uf._root(0)

ans='YES'
for i in range(n):
    if uf._root(i)!=p:
        ans='NO'

print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
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)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

N,M = IL()
data = ILL(N)

U = UnionFind(N+M)

for i in range(N):
  for g in data[i][1:]:
    U.union(g-1,i+M)

z = 0
for i in U.roots():
  if U.size(i) == 1:
    z += 1

if U.group_count() != z+1:
  print("NO")
else:
  print("YES")

Submission status: Accepted

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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def unite(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.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def get_size(self, x):
        return -self.table[self._root(x)]


n, m = map(int, input().split())
uft = UnionFind(n + m)
for i in range(n):
    k, *lll = map(int, input().split())
    for l in lll:
        uft.unite(i, l + n - 1)

for j in range(1, n):
    if not uft.find(0, j):
        print('NO')
        break
else:
    print('YES')

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
うーん，二部グラフっぽい？
言語と人の対応で，パスが8以内にあればOKみたいな
木の直径みたいな感じで行ける？
ある人から見て一番遠い人を1人選んで，その人から見て全員が8以内に入ればOKそう？
誤読っぽ，単純にUFで良いかも
"""

def main():
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        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=MI()
    uf=UnionFind(N+M)
    for i in range(N):
        L=LI()
        for j in range(1,L[0]+1):
            l=L[j]
            l-=1
            uf.union(i,l+N)
            
    roots=uf.roots()
    temp=0
    for v in roots:
        if v<N:
            temp+=1
        
            
    if temp<=1:
        print("YES")
    else:
        print("NO")
        

        
            
    
main()

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    global ok
    q = deque()
    q.append(1)
    ok[1] = 1
    while q:
        i = q.popleft()
        for j in G[i]:
            if ok[j] == 0:
                ok[j] = 1
                q.append(j)
    return

n, m = map(int, input().split())
G = [[] for _ in range(200001)]
for x in range(1, n + 1):
    l = list(map(int, input().split()))
    for i in range(1, l[0] + 1):
        y = l[i] + 100000
        G[x].append(y)
        G[y].append(x)
ok = [0] * 200001
bfs()
print("YES" if sum(ok[1 : n + 1]) == n else "NO")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[]
k=[]
g=set(())
d={}
cnt=0
for i in range(n):
  tmp=list(map(int,input().split()))
  k.append(tmp[0])
  l.append(tmp[1:])
  for j in tmp[1:]:
    if j in d:
      pass
    else:
      d[j]=cnt
      cnt+=1
mi=d.keys()
# Union FInd
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())
uf=UnionFind(len(mi))
for li in l:
  if len(li)==1:continue
  for x in li[1:]:
    uf.union(d[li[0]],d[x])
if uf.group_count()>1:
  print('NO')
else:
  print('YES')

Submission status: Accepted

Solution code:
class UnionFind:  # 0-index
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n  # 親の番号 要素が根の場合は-(そのグループの要素数)を格納

    def find(self, x):  # 要素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が属するグループと要素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):  # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):  # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):  # 要素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 {root: self.members(root) for root in self.roots()}

# ---------------------- #

n, m = (int(x) for x in input().split())
L = [tuple(int(x) for x in input().split()) for _ in range(n)]

uf = UnionFind(n + m)
for i in range(n):
    for l in L[i][1:]:
        l -= 1
        uf.union(i, n + l)

roots = uf.roots()
if len(roots) == 1 or roots[1] >= n:
    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())

    """
    n個の要素を0 ~ n - 1の番号で管理する。以下の属性およびメソッドを持つ。

    parents
    各要素の親要素の番号を格納するリスト
    要素が根（ルート）の場合は-(そのグループの要素数)を格納する

    find(x)
    要素xが属するグループの根を返す

    union(x, y)
    要素xが属するグループと要素yが属するグループとを併合する

    size(x)
    要素xが属するグループのサイズ（要素数）を返す

    same(x, y)
    要素x, yが同じグループに属するかどうかを返す

    members(x)
    要素xが属するグループに属する要素をリストで返す

    roots()
    すべての根の要素をリストで返す

    group_count()
    グループの数を返す

    all_group_members
    {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す

    __str__()
    print()での表示用
    ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
    """


n, m = (int(x) for x in input().split())
L = [set() for _ in range(n)]
for i in range(n):
    k, *arg = (int(x) for x in input().split())
    L[i].update(set(arg))

ANS = L[0]
uf = UnionFind(n)
for _ in range(100):
    for i in range(1, n):
        if ANS & L[i]:
            ANS |= L[i]
            uf.union(0, i)
    for i in reversed(range(1, n)):
        if ANS & L[i]:
            ANS |= L[i]
            uf.union(0, i)

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
belong=list()
group=list()

def init(X):
  global belong,group
  belong=list(range(X))
  group=[[i] for i in range(X)]

def unite(x,y):
  global belong,group
  if len(group[belong[x]])<len(group[belong[y]]):
    x,y=y,x
  if belong[x]==belong[y]:
    return True
  z=belong[y]
  for i in range(len(group[z])):
    belong[group[z][-1]]=belong[x]
    group[belong[x]].append(group[z][-1])
    del group[z][-1]
  return False

init(N+M)
L=[]
for i in range(N):
  L=list(map(int,input().split()))
  for j in range(L[0]):
    unite(i,L[j+1]+N-1)
if len(set(belong[:N]))==1:
  print('YES')
else:
  print('NO')

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(v):
        for u in edge[v]:
            if visited[u]:
                continue
            else:
                visited[u] = True
                dfs(u)

    n, m = map(int, input().split())
    edge = [[] for _ in range(n + m)]
    for i in range(n):
        _, *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)
    dfs(0)
    for i in range(n):
        if not visited[i]:
            print("NO")
            break
    else:
        print("YES")


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#CODE FESTIVAL 2016 Final-C
"""
グラフが連結であるかどうかを判定せよ？
距離が2以下になっているか判定せよかと思ったが、つながってればいいっぽい？
dfsで全部回れば良い
"""
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m = map(int,readline().split())
g = [[] for i in range(m)] #その言語を誰が使えるか
h = [] #誰がどの言語を使えるか
for i in range(n):
    lst1 = list(map(int,readline().split()))
    lst1 = lst1[1:]
    for j in lst1:
        g[j-1].append(i)
    h.append(lst1)


check = [0]*n
language = [0]*m
root = 0
check[root] = 1
deq = deque([root])
while deq:
    fr = deq.pop()
    for i in h[fr]:
        if language[i-1]:
            continue
        language[i-1] = 1
        for j in g[i-1]:
            if check[j]:
                continue
            deq.append(j)
            check[j] = 1


if all(i==1 for i in check):
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
from networkx import*
print('YES'*is_connected(Graph((i,j)for i in[*open(0)][1:]for j in i.split()[1:]))or'NO')

Submission status: Accepted

Solution code:
from networkx import*
print('NYOE S'[is_connected(Graph((t,j)for t in[*open(0)][1:]for j in t.split()[1:]))::2])

Submission status: Accepted

Solution code:
from networkx import*
print('NYOE S'[is_connected(Graph((i,j)for i,t in[*enumerate(open(0))][1:]for j in t.split()[1:]))::2])

Submission status: Accepted

Solution code:
from networkx import*
print('NYOE S'[is_connected(Graph([(i,j)for i,t in[*enumerate(open(0))][1:]for j in t.split()[1:]]))::2])

Submission status: Accepted

Solution code:
from networkx import*
g=[]
for t in[*open(i:=0)][1:]:
 i+=1
 for j in t.split()[1:]:g+=(i,j),
print('NYOE S'[is_connected(Graph(g))::2])

Submission status: Accepted

Solution code:
from networkx import*
g=[]
for t in[*open(i:=0)][1:]:
 for j in t.split()[1:]:g+=(i,'!'+j),
 i+=1
print('NYOE S'[is_connected(Graph(g))::2])

Submission status: Accepted

Solution code:
from networkx import*
g=[]
for _,*t in[*map(str.split,open(i:=0))][1:]:
 for j in t:g+=(i,'!'+j),
 i+=1
print('NYOE S'[is_connected(Graph(g))::2])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())  

par=[i for i in range(N+M)]
rank=[0]*(N+M)
friend=[0]*(N+M)
block=[0]*(N+M)
size=[1]*(N+M)

def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]

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

def union(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


for i in range(N):
  A=list(map(int, input().split()))
  a=A[0]
  A=A[1:]
  for j in A:
    union(i,N+j-1)
D=[]
for i in range(N):
  D.append(find(i))
if len(set(D))==1:
  print('YES')
else:
  print('NO')

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
from typing import Iterable
def main(N, M, KL):
    uf = UnionFindTree(N + M)
    for i, (K, *L) in enumerate(KL):
        for l in L:
            uf.union(i, N + l - 1)
    print('YES' if uf.same_all(range(N)) else 'NO')

class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.parent = [-1] * n

    def find(self, x: int) -> int:
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x: int, y: int) -> bool:
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

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

    def same_all(self, indices: Iterable[int]) -> bool:
        f, v = self.find, self.find(indices[0])
        return all(f(i) == v for i in indices)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    KL = [list(map(int, input().split())) for _ in range(N)]
    main(N, M, KL)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from typing import Iterable
import sys
def main(N, M, KL):
    uf = UnionFindTree(N + M)
    for i, (K, *L) in enumerate(KL):
        for l in L:
            uf.union(i, N + l - 1)
    print('YES' if uf.same_all(range(N)) else 'NO')

class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.parent = [-1] * n

    def find(self, x: int) -> int:
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x: int, y: int) -> bool:
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

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

    def same_all(self, indices: Iterable) -> bool:
        f, v = self.find, self.find(indices[0])
        return all(f(i) == v for i in indices)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    KL = [list(map(int, input().split())) for _ in range(N)]
    main(N, M, KL)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, M, KL):
    uf = UnionFindTree(N + M)
    for i, (K, *L) in enumerate(KL):
        for l in L:
            uf.union(i, N + l - 1)
    g = uf.find(0)
    for i in range(1, N):
        if uf.find(i) != g:
            break
    else:
        print('YES')
        return
    print('NO')

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

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

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

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    KL = [list(map(int, input().split())) for _ in range(N)]
    main(N, M, KL)

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)

    
    
n, m = map(int, input().split())
lang = []
for _ in range(n):
    a = [int(i) for i in input().split()[1:]]
    lang.append(a)    
un = UnionFind(n + m)

for i in range(n):
    for l in lang[i]:
        un.union(i, l + n)

ans = set([])
for i in range(n):
    k = un.find(i)
    ans.add(k)
    
if len(ans) == 1:
    print('YES')
else:
    print('NO')