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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

import sys

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

# if N > 1000 and M > 1000:
#     print("YES")
#     sys.exit()

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

lg = set(L[0])
update = True
used = [False] * N
used[0] = True
group = set(range(1, N))
while update:
    update = False
    re = []
    for i in group:
        if used[i]:
            continue
        for l in lg:
            if l in L[i]:
                used[i] = True
                lg = lg.union(set(L[i]))
                update = True
                re.append(i)
    group = group.difference(set(re))
# print(len(lg))
# print(lg)
if all(used):
    print("YES")
else:
    print("NO")

Submission status: Memory Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m = map(int, input().split())
adjacent_list = [[] for i in range(n+1+m+1)]
for i in range(1,n+1):
    for j in list(map(int, input().split()))[1:]:
        adjacent_list[i].append(j+n)
        adjacent_list[j+n].append(i)
finished = set()
def dfs(node):
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
dfs(1)
flag = True
for i in range(1,n+1):
    if i not in finished:
        flag = False
if flag:
    print("YES")
else:
    print("NO")

Submission status: Memory Limit Exceeded

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

N,M = map(int,input().split())
L = []
for i in range(N):
  tmp = list(map(int,input().split()))
  L.append(tmp[1:])
#print(L)

# 人(0~N-1)と言語(N~M-1)の間で二部グラフを作る
E = [set() for _ in range(N+M)]
for i in range(N):
  for l in L[i]:
    E[i].add(l+N-1)
    E[l+N-1].add(i)
#print(E)

# 人のノードすべてに到達可能であればYES
Visited = [0 for _ in range(N+M)]
def dfs(v):
  Visited[v] = 1
  for u in E[v]:
    if Visited[u] == 0:
      dfs(u)
dfs(0)
print('YES' if sum(Visited[:N]) == N else 'NO')

Submission status: Accepted

Solution code:
import sys
from networkx.utils import UnionFind
def input(): return sys.stdin.readline().rstrip()


def main():
    n,m=map(int, input().split())
    lang=[[] for i in range(m+1)]
    for i in range(1,n+1):
        for talk in list(map(int, input().split()))[1:]:
            lang[talk].append(i)
    uf = UnionFind()
    for langs in lang:
        if len(langs) >=1:
            uf.union(*langs)
    print('YES' if len(list(uf.to_sets()))==1 else 'NO')
    




if __name__ == '__main__':
    main()

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):
    lis=list(map(int,input().split()))
    for l in lis[1:]:
        l-=1
        edge[i].append(n+l)
        edge[n+l].append(i)
def bfs():
    visited=[0]*(n+m)
    q=deque([0])
    visited[0]=1
    while q:
        x=q.popleft()
        for nx in edge[x]:
            if visited[nx]==0:
                visited[nx]=1
                q.append(nx)
    return visited
visited=bfs()
if sum(visited[:n])==n:
    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, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
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 TUPLE(): return tuple(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 

#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if 0 > self.parents[x]:
            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 0 > x]
    # グループの数を返す
    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)

print("YES" if uf.group_count() == 1 else "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, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
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 TUPLE(): return tuple(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 

#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if 0 > self.parents[x]:
            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 0 > x]
    # グループの数を返す
    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()

language = [[] for _ in range(M)]
for i in range(N):
	K, *L = LIST()
	for l in L:
		language[l-1].append(i)

tree = UnionFind(N)
for x in language:
	if 2 <= len(x):
		tmp = x[0]
		for n in x[1:]:
			tree.union(tmp, n)
			tmp = n

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

Submission status: Accepted

Solution code:
class Union_Find:
  def __init__(self,n=0):
    self.vertices=n
    self.mother=[-1 for i in range(self.vertices)]
    self.size_temp=[1 for i in range(self.vertices)]
  
  def root(self,x):
    normalize_v=[]
    while x!=-1:
      normalize_v.append(x)
      y=x
      x=self.mother[x]
    for i in normalize_v[:-1]:
      self.mother[i]=y
    return y
  
  def union(self,x,y):
    root_x=self.root(x)
    root_y=self.root(y)
    if root_x!=root_y:
      self.mother[root_x]=root_y
      self.size_temp[root_y]+=self.size_temp[root_x]
  
  def find(self,x,y):
    if self.root(x)==self.root(y):
      return True
    else:
      return False
  
  def size(self,x):
    return self.size_temp[self.root(x)]
  
n,m=map(int,input().split())
l=[[] for i in range(m)]
for i in range(n):
  inp=list(map(lambda x:int(x)-1,input().split()))[1:]
  for j in inp:
    l[j].append(i)

uf=Union_Find(n)
for i in range(m):
  for j in range(len(l[i])-1):
    uf.union(l[i][j],l[i][j+1])
c=0
for i in range(n):
  c+=uf.root(i)==i
print("YES" if c==1 else "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)]

N, M = map(int,input().split())
UFT = UnionFind(N + M)
for i in range(N):
    K, *L = map(int,input().split())
    for l in L:
        UFT.union(i, N+l-1)

if len(set([UFT.find(i) for i in range(N)])) == 1:
    print('YES')
else:
    print('NO')

Submission status: Accepted

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

n,m = map(int,input().split())
s = [[] for i in range(m+1)]
u = Unionfind(n)
for i in range(n):
    l = list(map(int,input().split()))
    for j in l[1:]:
        if s[j]:
            u.union(i,s[j][0])
        else:
            s[j].append(i)
if u.size(0) == n:
    print("YES")
else:
    print("NO")

Submission status: Accepted

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


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


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


def read_float():
    return float(readline())


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


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


def read_str_n():
    return readline().strip().split()


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


def mt(f):
    import time

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

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

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g


@mt
def slv(N, M, L):
    lo = 10**6
    uf = UnionFind()
    for i, l in enumerate(L):
        for j in l:
            uf.union(i, j+lo)

    return 'YES' if all(uf.same(0, i) for i in range(1, N)) else 'NO'


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


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


def read_float():
    return float(readline())


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


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


def read_str_n():
    return readline().strip().split()


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


def mt(f):
    import time

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

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

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g

@mt
def slv(N, M, L):
    lo = 10**6
    uf = UnionFind()
    for i, l in enumerate(L):
        for j in l:
            uf.union(i, j+lo)


    return 'YES' if all(uf.same(0, i) for i in range(1, N)) else 'NO'








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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

N,M = list(map(int,input().split()))
Network = UnionFind(N+M)
for i in range(N):
    tmp = list(map(int,input().split()))
    for j in range(tmp[0]):
        Network.union(i, tmp[j+1]+N-1)
cnt = 0
for k in Network.parents:
    if k<0 and k!= -1:
        cnt += 1
if cnt>=2:
    print("NO")
else:
    print("YES")

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def find(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.find(self.root[x])
      return self.root[x]
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if(x == y):
      return 
    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 same(self, x, y):
    return self.find(x) == self.find(y)
  def count(self, x):
    return -self.root[self.find(x)]
n,m=map(int,input().split())
e=[[]for _ in range(m)]
uf=UnionFind(n)
for i in range(n):
  k,*lk,=map(int,input().split())
  for j in lk:
    e[j-1]+=[i]
for i in e:
  if not i:continue
  k=i[0]
  for j in i[1:]:
    uf.unite(k,j)
print(['NO','YES'][uf.count(0)==n])

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

n, m = map(int, input().split())
UF = UnionFind(n + m)
for i in range(n):
    kl = list(map(int, input().split()))
    l_s = kl[1:]
    for l in l_s:
        UF.union(i, l - 1 + n)

for i in range(1, n):
    if not UF.same(i, 0):
        print("NO")
        exit()
print("YES")

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


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):
        ret = dict()
        for i in range(self.n):
            r = self.find(i)
            if r in ret:
                ret[r].append(i)
            else:
                ret[r] = [i]
        return ret

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


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

    lang = [[] for _ in range(M)]
    for i in range(N):
        line = in_nl()
        for j in range(1, len(line)):
            lang[line[j] - 1].append(i)

    uni = UnionFind(N)

    # print(lang)

    for i in range(M):
        for j in range(len(lang[i]) - 1):
            uni.union(lang[i][j], lang[i][j + 1])
            # print(lang[i][j], lang[i][j + 1])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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:
# メモ：問題文と解答がかみ合ってない気がする。
# そもそも「入力例 1」で「人1・4は2とコミュニケーション取れる」とあるが、
# これは定義に反している気がする。
# 人1・4に共通言語はないし、人1・4がコミュニケーション取るには1人では無理（人2・3両方必要）。

from collections import defaultdict


class UnionFind:

    def __init__(self, n):
        self.n = n
        # root[x] < 0ならそのノードが根かつその絶対値が木の要素数
        self.root = [-1] * (n + 1)
        self.rank = [0] * (n + 1)

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

    def union(self, one_node, other_node):
        one_node = self.find_root(one_node)
        other_node = self.find_root(other_node)
        if one_node == other_node:
            return
        elif self.rank[one_node] > self.rank[other_node]:
            self.root[one_node] += self.root[other_node]
            self.root[other_node] = one_node
        else:
            self.root[other_node] += self.root[one_node]
            self.root[one_node] = other_node
            if self.rank[one_node] == self.rank[other_node]:
                self.rank[other_node] += 1

    def group_size(self, node):
        return - self.root[self.find_root(node)]


def main():
    N, M = list(map(int, input().split()))
    lang_member_map = defaultdict(list)
    for n in range(N):
        for lang in input().split()[1:]:
            lang_member_map[lang].append(n)
    tree = UnionFind(N)
    for members in lang_member_map.values():
        if len(members) <= 1:
            continue
        n1 = members[0]
        for n2 in members[1:]:
            tree.union(n1, n2)
    if tree.group_size(0) == N:
        print('YES')
    else:
        print('NO')


if __name__ == '__main__':
    main()