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:
import array

def solve():
    n, m = map(int, input().split())
    humanSpeakLanguages = []
    for _ in range(n):
        language = array.array("I", [int(i) for i in input().split()])
        humanSpeakLanguages.append(language[1:])
    humanSpeakLanguages.sort()
    stack = set(humanSpeakLanguages[0])
    humanSpeakLanguages.pop(0)
    while len(stack) > 0 and len(humanSpeakLanguages) > 0:
        targetLanguage = stack.pop()
        removeIdxs = array.array("i")
        for (i, language) in enumerate(humanSpeakLanguages):
            if targetLanguage in language:
                stack |= set(language)
                removeIdxs.append(i)

        for elem in removeIdxs[::-1]:
            humanSpeakLanguages.pop(elem)

    if len(humanSpeakLanguages) > 0:
        print("NO")
    else:
        print("YES")

if __name__=="__main__":
    solve()

Submission status: Time Limit Exceeded

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


graph = []
graph2 = [[] for i in range(M)]
for i in range(N):
    foo = list(map(int , input().strip().split(" ")))
    del foo[0]
    graph.append(foo)
    for j in foo:
        graph2[j-1].append(i)


stack = [0]
visited = []
while stack:
    label = stack.pop(0)
    if label not in visited:
        visited.append(label)
        foo = []
        for i in graph[label]:
            if(len(graph2[i-1]) ==1) : continue
            for  j in graph2[i-1]:
                if j not in visited:
                    stack.append(j)
            

#print(visited)
if len(visited) == N : 
    print('YES')
else:
    print('NO')

Submission status: Time Limit Exceeded

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


graph = []
graph2 = [[] for i in range(M)]
for i in range(N):
    foo = list(map(int , input().strip().split(" ")))
    del foo[0]
    graph.append(foo)
    for j in foo:
        graph2[j-1].append(i)


stack = [0]
visited = []
while stack:
    label = stack.pop(0)
    if label not in visited:
        visited.append(label)
        foo = []
        for i in graph[label]:
            if(len(graph2[i-1]) ==1) : continue
            for  j in graph2[i-1]:
                stack.append(j)
            

#print(visited)
if len(visited) == N : 
    print('YES')
else:
    print('NO')

Submission status: Time Limit Exceeded

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


graph = []
graph2 = [[] for i in range(M)]
for i in range(N):
    foo = list(map(int , input().strip().split(" ")))
    del foo[0]
    graph.append(foo)
    for j in foo:
        graph2[j-1].append(i)


stack = [0]
visited = []
while stack:
    label = stack.pop(0)
    if label not in visited:
        visited.append(label)
        foo = []
        for i in graph[label]:
            for j in graph2[i-1]:
                stack.append(j)
            

#print(visited)
if len(visited) == N : 
    print('YES')
else:
    print('NO')

Submission status: Time Limit Exceeded

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


graph = []
graph2 = [[] for i in range(M)]
for i in range(N):
    foo = list(map(int , input().strip().split(" ")))
    del foo[0]
    graph.append(foo)
    for j in foo:
        graph2[j-1].append(i)


stack = [0]
visited = []
while stack:
    label = stack.pop(0)
    if label not in visited:
        visited.append(label)
        foo = []
        for i in graph[label]:
            for j in graph2[i-1]:
                if j not in visited:
                    stack.append(j)
            

#print(visited)
if len(visited) == N : 
    print('YES')
else:
    print('NO')

Submission status: Time Limit Exceeded

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

lines = sys.stdin.readlines()

N, M = lines[0].strip().split(" ")

ppl = []
for line in lines[1:]:
    langs = line.strip().split(" ")[1:]
    ppl.append(set(langs))

def can_comunicate(p1, p2):
    return len(p1.intersection(p2)) > 0

clang = ppl.pop()
num_lang = len(clang)
rest = []
while True:
    for p in ppl:
        if can_comunicate(clang, p):
            clang = clang.union(p)
        else:
            rest.append(p)

    if len(rest) == 0:
        print 'YES'
        break
    elif len(clang) > num_lang:
        ppl = rest
        rest = []
        num_lang = len(clang)
        pass # もう一回
    else: # 新しい言語が増えず、話せない人がいる
        print 'NO'
        break

Submission status: Time Limit Exceeded

Solution code:
import array

def solve():
    n, m = map(int, input().split())
    humanSpeakLanguages = []
    for _ in range(n):
        language = array.array("I", [int(i) for i in input().split()])
        humanSpeakLanguages.append(language[1:])
    stack = set(humanSpeakLanguages[0])
    humanSpeakLanguages.pop(0)
    while len(stack) > 0 and len(humanSpeakLanguages) > 0:
        targetLanguage = stack.pop()
        removeIdxs = array.array("i")
        for (i, language) in enumerate(humanSpeakLanguages):
            if targetLanguage in language:
                stack |= set(language)
                removeIdxs.append(i)

        for elem in removeIdxs[::-1]:
            humanSpeakLanguages.pop(elem)


    if len(humanSpeakLanguages) > 0:
        print("NO")
    else:
        print("YES")

if __name__=="__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import array

def solve():
    n, m = map(int, input().split())
    humanSpeakLanguages = []
    for _ in range(n):
        language = tuple(input().split())
        humanSpeakLanguages.append(language[1:])
    stack = set(humanSpeakLanguages[0])
    humanSpeakLanguages.pop(0)
    while len(stack) > 0 and len(humanSpeakLanguages) > 0:
        # なんか適当に取り出す
        targetLanguage = stack.pop()
        removeIdxs = array.array("i")
        for (i, language) in enumerate(humanSpeakLanguages):
            if targetLanguage in language:
                stack |= set(language)
                removeIdxs.append(i)

        for elem in removeIdxs[::-1]:
            humanSpeakLanguages.pop(elem)


    if len(humanSpeakLanguages) > 0:
        print("NO")
    else:
        print("YES")

if __name__=="__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

people = defaultdict(set)

n, _ = map(int, next(sys.stdin).strip().split())

for i, line in enumerate(sys.stdin):
    _, *langs = line.strip().split()
    new = {i}
    for lang in langs:
        old = people[lang]
        new.update(old)
        for l in people.keys():
            if people[l] is old:
                people[l] = new

if len(next(people.values())) == n:
    print('YES')
else:
    print('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:
import sys
input = sys.stdin.readline

class UnionFind():
    """unionFindツリー
    FindとUnionがきも
    https://note.nkmk.me/python-union-find/
    """
    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

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

uf = UnionFind(N+M)
for i in range(N):
  li = list(map(int, input().split()))
  for j in li[1:]:
    uf.union(i,N+j-1)
    
p = uf.find(0)
for i in range(1,N):
  q = uf.find(i)
  #print(p,q)
  if p != q:
    print("NO")
    exit(0)
    
print("YES")

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.height = [1] * n
        self.size = [1] * 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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.height[x] < self.height[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.height[x] == self.height[y]:
                    self.height[x] += 1

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


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

uf = UnionFind(M)
lang = set()
for _ in range(N):
    KL = tuple(map(int, input().split()))
    for i in range(1, KL[0]):
        uf.unite(KL[i] - 1, KL[i + 1] - 1)  # 0-indexed
    for i in range(KL[0]):
        lang.add(KL[i + 1] - 1)

lang = list(lang)
print('YES' if uf.group_size(lang[0]) == len(lang) else 'NO')

Submission status: Accepted

Solution code:
class Union_Find():
    def __init__(self, num):
        self.par = [-1]*(num+1)
        self.siz = [1]*(num+1)

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

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

    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.siz[ry] += self.siz[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
        return

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

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

tree = Union_Find(n)
for i in range(1, m+1):
    for j in range(len(lang[i])-1):
        tree.union(lang[i][j+1], lang[i][j])

if tree.size(0) == n:
    print("YES")
else:
    print("NO")

Submission status: Accepted

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

n, m = map(int, input().split())
row = []
col = []
for i in range(n):
    k, *l = map(int, input().split())
    row += [i] * k
    col += [e + n - 1 for e in l]

cost = [1] * len(row)

graph = csr_matrix((cost, (row, col)), shape=(n + m, n + m))
_, labels = connected_components(graph)

bl = (labels[:n] == labels[0]).all()
print("YES" if bl else "NO")

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


n, m = map(int, input().split())
l = []
for _ in range(n):
    k, *ls = map(int, input().split())
    l.append(ls)

uf = UnionFind(m)

for li in l:
    for e1, e2 in zip(li, li[1:]):
        e1 -= 1
        e2 -= 1
        uf.unite(e1, e2)

p = uf.find_set(l[0][0] - 1)
ans = "YES"
for e, *_ in l:
    if uf.find_set(e - 1) != p:
        ans = "NO"

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def get_par(par, p):
    while par[p] != p:
        p = par[p]
    return par[p]

n,m = map(int, input().split())
lang = {}
for i in range(n):
    k,*l = map(int, input().split())
    for j in l:
        # print(i,j)
        if j not in lang:
            lang[j] = []
        lang[j].append(i)
# [print(k,v) for k,v in lang.items()]

par = [i for i in range(n)]
for k,v in lang.items():
    if len(v) == 1:
        continue
    a = v[0]
    for i in range(1,len(v)):
        aa = get_par(par, a)
        bb = get_par(par, v[i])
        if aa == bb:
            continue
        # unite
        if aa < bb:
            par[bb] = aa
        else:
            par[aa] = bb

ans = [get_par(par, i) for i in range(n)]
print('YES' if len(set(ans)) == 1 else 'NO')
# print(par)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
N, M = map(int, input().split())
K = [0]*(N+1)
L = [[] for _ in range(N+1)]
graph = [[] for _ in range(N+M+1)]
for i in range(1, N+1):
    K[i], *L[i] = map(int, input().split())
    for lang in L[i]:
        graph[i].append(lang + N)
        graph[lang + N].append(i)

seen = [False] * (N+M+1)
person = [0] * (N+1)


def dfs(node, seen):
    here = node
    seen[here] = True
    #print(f"here: {here}")
    if here <= N:
        person[here] = 1
    for goto in graph[here]:
        if not seen[goto]:
            dfs(goto, seen)


dfs(1, seen)
print("YES" if sum(person) == N else "NO")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
import sys;sys.setrecursionlimit(10**9)
class Union_Find():
  def __init__(self,n):self.n,self.r=[-1]*n,[0]*n
  def Find_Root(self,x):
    if self.n[x]<0:return x
    else:self.n[x]=self.Find_Root(self.n[x]);return self.n[x]
  def Unite(self,x,y):
    x,y=self.Find_Root(x),self.Find_Root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:self.n[x]+=self.n[y];self.n[y]=x
    else:self.n[y]+=self.n[x];self.n[x]=y;self.r[y]+=self.r[x]==self.r[y]
  def isRootSame(self,x,y):return self.Find_Root(x)==self.Find_Root(y)
  def Count(self,x):return -self.n[self.Find_Root(x)]
u=Union_Find(m)
l=[list(map(int,input().split()))for _ in range(n)]
for i in range(n):
  for j in range(1,len(l[i])-1):u.Unite(l[i][j]-1,l[i][j+1]-1)
for i in range(n-1):
  if not(u.isRootSame(l[i][1]-1,l[i+1][1]-1)):print("NO");exit()
print("YES")

Submission status: Accepted

Solution code:

def wantp(n):

    l = []
    while p[n] != n:
        l.append(n)
        n = p[n]

    for i in l:
        p[i] = n

    return n



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

dic = {}

for i in range(N):

    kl = list(map(int,input().split()))

    for j in range(kl[0]):

        j += 1
        if kl[j] not in dic:
            dic[kl[j]] = []

        dic[kl[j]].append(i)

p = [i for i in range(N)]
rank = [1] * N

for i in dic:

    if i not in dic:
        continue

    for j in range(len(dic[i]) - 1):

        a = dic[i][j]
        b = dic[i][j+1]

        ap = wantp(a)
        bp = wantp(b)

        if ap != bp:

            if rank[ap] > rank[bp]:
                p[bp] = ap
            elif rank[ap] < rank[bp]:
                p[ap] = bp
            else:
                p[ap] = bp
                rank[bp] += 1

n = 0
for i in range(N):
    if i == wantp(p[i]):
        n += 1

#print (p,dic)
if n == 1:
    print ("YES")
else:
    print ("NO")

Submission status: Accepted

Solution code:
from functools import reduce

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        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 と 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.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
      
n,m = map(int, input().split())
l = [list(map(int, input().split()))[1:] for i in range(n)]
langs = [list() for i in range(m)]
for p,i in enumerate(l):
  for lang in i:
    langs[lang-1].append(p)
commu = UnionFind(n)
for i in langs:
  if i:
    now = i[0]
    for j in i[1:]:
      commu.union(now,j)
      now = j
if commu.get_size(0) == n:
  print("YES")
else:
  print("NO")

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
V = range(N+M)
E = defaultdict(list)
for i in range(N):
    _, *L, = map(int, input().split())
    for l in L:
        l -= 1
        E[i].append(l+N)
        E[l+N].append(i)
stack = [0]
visited = [False] * (N+M)
while stack:
    i = stack.pop()
    if visited[i]: continue
    visited[i] = True
    for j in E[i]:
        if not visited[j]:
            stack.append(j)
if sum(visited[:N]) == N:
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
# unionfind
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]

N, M = map(int, input().split())
C = [False] * (M+1)
uf = Uf(M+1)
for _ in range(N):
    K, *L = map(int, input().split())
    l0 = L[0]
    C[l0] = True
    for l in L[1:]:
        uf.unite(l0, l)
        C[l] = True
roots = [uf.root(i) for i, c in enumerate(C) if c]
print("YES" if len(set(roots))==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 main():
    N, M = map(int, input().split())
    uni = UnionFind(N + M)
    for i in range(N):
        K, *L = map(int, input().split())
        for l in L:
            uni.union(i, N + l - 1)
    
    root = set()
    for i in range(N):
        root.add(uni.find(i))
    
    if len(root) == 1:
        print('YES')
    else:
        print('NO')



main()

Submission status: Accepted

Solution code:
n,m = map(int,input().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):
        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(n)
people = [[]for i in range(m)]
for i in range(n):
    a = list(map(int,input().split()))
    n1 = a.pop(0)
    for j in range(n1):
        if len(people[a[j]-1]) == 0:
            people[a[j]-1].append(i)
        else:
            uf.union(people[a[j]-1][0],i)
if uf.group_count() == 1:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque

parent_node = []

def union_find(ele):
    global parent_node
    if parent_node[ele] != ele:
        parent_node[ele] = union_find(parent_node[ele])
    return parent_node[ele]

def main():
    num, lang_num = map(int, input().split())

    graph_data = defaultdict(set)
    for i in range(num):
        data = list(map(int, input().split()))
        for ele in data[1:]:
            graph_data[ele].add(i + 1)

    global parent_node
    parent_node = [i for i in range(num + 1)]




    for key, value in graph_data.items():
        min_set = set([union_find(ele) for ele in value])
        min_ind = min(list(min_set))
        for ele in min_set:
            parent_node[ele] = min_ind

    for i in range(num + 1):
        a = union_find(i)

    # print(parent_node)

    if max(parent_node) == 1:
        print('YES')
    else:
        print('NO')









if __name__ == '__main__':
    main()

Submission status: Accepted

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

    def root(self, x):
        """頂点xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """頂点xを含む集合と頂点y含む集合を結合する"""
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.parent[x] > self.parent[y]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        return

    def is_same(self, x, y):
        """頂点xと頂点yが同じ集合に属するかどうかを返す"""
        return self.root(x) == self.root(y)

    def get_size(self, x):
        '''頂点xを含む集合の要素数を返す'''
        return -self.parent[self.root(x)]


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

li = [[] for i in range(m)]
for i in range(n):
    for num in info[i][1:]:
        li[num - 1].append(i)

uf = UnionFind(n)
for li_ in li:
    for i in range(len(li_) - 1):
        if not uf.is_same(li_[i], li_[i + 1]):
            uf.merge(li_[i], li_[i + 1])

if uf.get_size(0) == n:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

class UnionFind :
    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        root1 = self.root(index1)
        root2 = self.root(index2)

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

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

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

    def isSameRoot(self, index1, index2) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component


def sol():
    N, M = map(int, input().split())

    tree = UnionFind(N + M)

    for person in range(N):
        line = list(map(int, input().split()))
        for lang in line[1:]:
            tree.union(person, N + lang - 1)

    rootList = set()
    for person in range(N):
        rootList.add(tree.root(person))

    if len(rootList) == 1:
        print('YES')
    else:
        print('NO')

sol()

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.root(x)]


N, M = list(map(int, sys.stdin.readline().split()))
uf = UnionFind(size=N + M + 1)
for i in range(N):
    _, *L = list(map(int, sys.stdin.readline().split()))
    for lang in L:
        uf.unite(i, N + lang)

ok = True
root = uf.root(0)
for i in range(N):
    ok &= root == uf.root(i)
if ok:
    print("YES")
else:
    print("NO")