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 defaultdict
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

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

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


N, M = map(int, input().split())
Un = UnionFind(N)  # 会話できる人をつなげる
D = defaultdict(lambda: [])
for i in range(N):
    _, *L = map(lambda x: int(x)-1, input().split())
    for l in L:
        D[l].append(i)
for i in range(M):
    if len(D[i]) > 1:
        t = D[i]
        for d in t[1:]:
            Un.union(t[0], d)
print("YES" if Un.connectedNum(0) == N else "NO")

Submission status: Accepted

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


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

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

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


N, M = map(int, input().split())
Un = UnionFind(N)  # 会話できる人をつなげる
D = defaultdict(lambda: [])
for i in range(N):
    _, *L = map(lambda x: int(x)-1, input().split())
    for l in L:
        D[l].append(i)
for i in range(M):
    if len(D[i]) > 1:
        t = D[i]
        for d in t[1:]:
            Un.union(t[0], d)
if Un.size[Un.find(0)] == N:
    print("YES")
else:
    print("NO")

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)

    def ans(self):
        return (len(set(self.par))-1)

n,m=map(int,input().split())
uf=UnionFind(n)
l=[[] for i in range(m)]
for i in range(n):
    k=list(map(int,input().split()))
    k=k[1:]
    for j in k:
        l[j-1].append(1+i)
    
for i in range(m):
    if len(l[i])>0:
        ll=l[i][0]
        for j in range(len(l[i])-1):
            uf.union(ll,l[i][j+1])

for i in range(1,n+1):
    uf.find(i)

if uf.ans()==1:
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]
uf = UnionFind(N + M)
for i in range(N):
  l = list(map(int, input().split()))
  for j in range(1, l[0] + 1):
    uf.Unite(i + 1, l[j] + N)
p = -1
for i in range(1, N + 1):
  if uf.Find_Root(i) == i and p == -1:
    p = i
  elif p == -1:
    p = uf.Find_Root(i)
  elif uf.Find_Root(i) != p:
    p = -1
    break
  elif uf.Find_Root(i) == -1 and p != -1:
    p = -1
    break
if p == -1:
  print("NO")
else:
  print("YES")

Submission status: Accepted

Solution code:
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

#xが属する集合の個数
def size(x):
    return -par[find(x)]

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

#根なら-size,子なら親の頂点
par = [-1]*n
lan = [[] for _ in [0]*m]
for pt in range(n):
    l = tuple(map(int,input().split()))
    for i in range(1,len(l)):
        lan[l[i]-1].append(pt)

for i in range(m):
    for j in range(1,len(lan[i])):
        unite(lan[i][0],lan[i][j])

cnt = 0
for e in par:
    if e < 0:
        cnt += 1

if cnt == 1:
    print('YES')
else:
    print('NO')

Submission status: Accepted

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~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
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 併合
    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
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

n,m=map(int,input().split())
kl=[list(map(int,input().split())) for i in range(n)]
uf=UnionFind(m)
for i in range(n):
    for j in range(2,kl[i][0]+1):    
        uf.union(kl[i][1], kl[i][j])

for i in range(1,n):
    if not uf.same_check(kl[0][1],kl[i][1]):
        print("NO")
        quit()
print("YES")

Submission status: Accepted

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

# 人[0, N) 言語[N N+M)
ad = [[] for _ in range(N+M)]

for i in range(N):
    for l in L[i]:
        l -= 1
        ad[i].append((l+N, 1))
        ad[l+N].append((i, 1))

from heapq import heappush, heappop
inf = float('inf')

# 計算量O((E+V)logV)
# 引数(始点,隣接リスト)
def dijkstra(start,ad):
    global dist
    #global cnt
    N = len(ad)
    dist = [inf] * N
    dist[start] = 0
    #cnt = [0] * N
    #cnt[start] = 1
    pq = [(dist[start], start)]
    while pq:
        dist_v, v = heappop(pq)
        for nv, nw in ad[v]:
            if dist[nv] > dist_v + nw:
                dist[nv] = dist_v + nw
                heappush(pq,(dist[nv], nv))
            #if dist[nv] == dist_v + nw:
                #cnt[nv] += cnt[v]
                #cnt[nv] %= mod

dijkstra(0, ad)

for i in range(N):
    if dist[i] == inf:
        print("NO")
        exit()

print("YES")

Submission status: Accepted

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

lang = [[] for _ in range(M)]

for i in range(N):
    L = list(map(int,input().split()))[1:]
    for l in L:
        l -= 1
        lang[l].append(i)

class Unionfind:

    __slots__ = ['nodes','size']

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

    def root(self, x):
        if self.nodes[x] == x:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.nodes[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.size[x] += self.size[y]
        self.nodes[y] = x

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

    def kind(self):
        for v in range(N):
            self.root(v)
        return len(list(set(self.nodes)))

uf = Unionfind(N)

for group in lang:
    for i in range(len(group)-1):
        v = group[i]
        nv = group[i+1]
        uf.unite(v, nv)

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

Submission status: Accepted

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


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

    # 検索
    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 groupsize(self):
        self.cnt = 0
        for i,x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.root[x] += self.root[y]
            self.root[y] = self.root[x]
        else:
            self.par[y] = x
            self.root[x] += self.root[y]
            self.root[y] = self.root[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 count(self, x):
        return -self.root[self.find(x)]
    
    
uf = UnionFind(M)
for lk in L:
    l = lk[1:]
    if len(l) > 0:
        base = l[0]-1
        for i in range(1,len(l)):
            uf.union(base,l[i]-1)
            
isUsed = [False] * M
for lk in L:
    for l in lk[1:]:
        isUsed[l-1] = True


looplist = [i for i in range(M) if isUsed[i]]
tmp1 = looplist[0]
for i in looplist[1:]:
    if not(uf.same_check(tmp1,i)):
        print('NO')
        break
else:
    print('YES')

Submission status: Accepted

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


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

    # 検索
    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 groupsize(self):
        self.cnt = 0
        for i,x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.root[x] += self.root[y]
            self.root[y] = self.root[x]
        else:
            self.par[y] = x
            self.root[x] += self.root[y]
            self.root[y] = self.root[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 count(self, x):
        return -self.root[self.find(x)]
    
    
uf = UnionFind(M)
for lk in L:
    l = lk[1:]
    if len(l) > 0:
        base = l[0]-1
        for i in range(1,len(l)):
            uf.union(base,l[i]-1)
            
isUsed = [False] * M
for lk in L:
    for l in lk[1:]:
        isUsed[l-1] = True


looplist = [i for i in range(M) if isUsed[i]]
tmp1 = looplist[0]
for i in looplist[1:]:
    if not(uf.same_check(tmp1,i)):
        print('NO')
        break
else:
    print('YES')

Submission status: Accepted

Solution code:
import sys
import heapq
import bisect
import itertools

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def LI_(): return([int(x)-1 for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    N,M = LI()
    ll = [[] for _ in range(N)]
    dic = {}
    for i in range(N):
        KL = LI()
        ll[i] = [j-1 for j in KL[1:]]
        for l in KL[1:]:
            dic[l-1] = dic.get(l-1,[])
            dic[l-1].append(i)

    flagk = [True] * N
    flagl = {}
    for l in dic:
        flagl[l] = True

    que = [0]
    while que:
        k = que.pop()
        if flagk[k]:
            flagk[k] = False
            for l in ll[k]:
                if flagl[l]:
                    flagl[l] = False
                    for nxt in dic[l]:
                        if flagk[nxt]:
                            que.append(nxt)
    for x in flagk:
        if x:
            return("NO")
    return("YES")



if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
# cf16-finalC - Interpretation
class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size + 1)]
        self.rank = [0] * (size + 1)

    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        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 main():
    N, M = map(int, input().split())
    A = [(map(int, input().split())) for _ in range(N)]
    uf, spoken = UnionFind(M), set()
    for _, *langs in A:
        spoken.update(langs)
        primary = langs[0]
        for l in langs[1:]:
            uf.unite(primary, l)
    cur = uf.find(spoken.pop())
    flg = all(uf.find(lang) == cur for lang in spoken)
    print("YES" if flg else "NO")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# cf16-finalC - Interpretation
class UnionFind:  # O(α(N))
    def __init__(self, size):  # construct a Union-Find tree (1-idx)
        self.parent = [i for i in range(size + 1)]
        self.rank = [0] * (size + 1)

    def find(self, x):  # find the group (root) of a vertex
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):  # unite two groups
        x, y = self.find(x), self.find(y)
        if x == y:  # in the same group
            return
        # unite a small one to a bigger one to balance trees
        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 main():
    # Union-Find on spoken languages -> check all langs are in the same group?
    N, M = map(int, input().split())
    A = [(map(int, input().split())) for _ in range(N)]
    uf, spoken = UnionFind(M), set()
    for _, *langs in A:
        spoken.update(langs)
        primary = langs[0]  # primary language for the person
        for l in langs[1:]:
            uf.unite(primary, l)
    cur = uf.find(spoken.pop())  # group of one of spoken languages
    flg = all(uf.find(lang) == cur for lang in spoken)
    print("YES" if flg else "NO")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# cf16-finalC - Interpretation
class UnionFind:  # O(α(N))
    def __init__(self, size):  # construct a Union-Find tree (1-idx)
        self.parent = [i for i in range(size + 1)]
        self.rank = [0] * (size + 1)

    def find(self, x):  # find the group (root) of a vertex
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):  # unite two groups
        x, y = self.find(x), self.find(y)
        if x == y:  # in the same group
            return
        # unite a small one to a bigger one to balance trees
        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 main():
    # Union-Find on spoken languages -> check all langs are in the same group?
    N, M = map(int, input().split())
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    uf, spoken = UnionFind(M), set()
    for _, *langs in A:
        spoken.update(langs)
        primary = langs[0]
        for l in langs[1:]:
            uf.unite(primary, l)
    cur = uf.find(spoken.pop())  # group of one of spoken languages
    flg = all(uf.find(lang) == cur for lang in spoken)
    print("YES" if flg else "NO")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# cf16-finalC - Interpretation
class UnionFind:  # O(α(N))
    def __init__(self, size):  # construct a Union-Find tree (1-idx)
        self.parent = [i for i in range(size + 1)]
        self.rank = [0] * (size + 1)

    def find(self, x):  # find the group (root) of a vertex
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def is_same(self, x, y):  # check two vertices are in the same group
        return self.find(x) == self.find(y)

    def unite(self, x, y):  # unite two groups
        x, y = self.find(x), self.find(y)
        if x == y:  # in the same group
            return
        # unite a small one to a bigger one to balance trees
        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 main():
    N, M = map(int, input().split())
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    uf, spoken = UnionFind(M), set()
    for _, *langs in A:
        spoken.update(langs)
        primary = langs[0]
        for l in langs[1:]:
            uf.unite(primary, l)
    cur = uf.find(spoken.pop())
    flg = all(uf.find(lang) == cur for lang in spoken)
    print("YES" if flg else "NO")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# cf16-finalC - Interpretation
# bipartite graph
def dfs() -> None:
    stack = [(1, 1)]
    seen_m[1] = 1
    while stack:
        v, flg = stack.pop()
        if flg:
            for u in men[v]:
                if not seen_l[u]:
                    stack.append((u, 0))
                    seen_l[u] = 1
        else:
            for u in langs[v]:
                if not seen_m[u]:
                    stack.append((u, 1))
                    seen_m[u] = 1


def main():
    global men, langs, seen_m, seen_l
    N, M = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(N))
    men, langs = [[] for _ in range(N + 1)], [[] for _ in range(M + 1)]
    for person, lang in enumerate(A, 1):  # construct a bipartite graph
        for l in lang[1:]:
            men[person].append(l), langs[l].append(person)
    seen_m, seen_l = [0] * (N + 1), [0] * (M + 1)
    dfs()
    flg = all(i for i in seen_m[1:])
    print("YES" if flg else "NO")


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def same_tree(node_a, node_b):
    if node_a.root() == node_b.root():
        return True

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    N, M = map(int, input().split())
    kl = [list(map(int, input().split())) for i in range(N)]

    nodes = [Node() for i in range(M)]
    peaple = [Node() for i in range(N)]

    for i in range(N):
        l = kl[i][1:]
        peaple[i].is_root = False
        peaple[i].parent = nodes[l[0]-1]
        for j in range(1, len(l)):
            unite(nodes[l[j]-1], nodes[l[j-1]-1])
    
    ok = True
    for i in range(1, N):
        if not same_tree(peaple[0], peaple[i]):
            ok = False
    
    if ok:
        print("YES")
    else:
        print("NO")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
par=[-1]*(n+m)

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

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return False
  else:
    if par[x]>par[y]:
      x,y=y,x
    par[x]+=par[y]
    par[y]=x
    return True

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

def size(x):
  return -par[find(x)]

for i in range(n):
  KL=[int(i) for i in input().split()]
  for j in range(1,len(KL)):
    unite(i,n+KL[j]-1)
chk=True
for i in range(1,n):
  if not same(0,i):
    chk=False
print("YES" if chk==True else "NO")

Submission status: Accepted

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

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)

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

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


N, M = map(int, input().split())
uf = UnionFind(M + 1)
used = set()
for _ in range(N):
    K, *L = map(int, input().split())
    for l in L:
        uf.union(L[0], l)
    used.update(L)

if uf.size(used.pop()) == 1 + len(used):
    print("YES")
else:
    print("NO")

Submission status: Accepted

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

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)

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

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


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

if uf.size(1) - len(used) == N:
    print("YES")
else:
    print("NO")

Submission status: Accepted

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

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)

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

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


N, M = map(int, input().split())
uf = UnionFind(N + M + 1)
used = [False] * (M + 1)
for i in range(1, N + 1):
    K, *L = map(int, input().split())
    for l in L:
        uf.union(i, l + N)
        used[l] = True

if uf.size(1) - sum(used) == N:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
class UnionFind:
	def __init__(self, size):
		self.data = [-1] * size
	def find(self, x):
		if self.data[x] < 0:
			return x
		else:
			self.data[x] = self.find(self.data[x])
			return self.data[x]
	def union(self, x, y):
		x, y = self.find(x), self.find(y)
		if x != y:
			if self.data[y] < self.data[x]:
				x, y = y, x
			self.data[x] += self.data[y]
			self.data[y] = x
		return (x != y)
	def same(self, x, y):
		return (self.find(x) == self.find(y))

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

if all(uf.same(i, N) for i in range(1, N)):
	print("YES")
else:
	print("NO")

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.data = [-1 for _ in range(size)]
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

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

if all(uf.same(i, N) for i in range(1, N)):
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
from collections import deque

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

es_lang = [[] for _ in range(M+1)] # 各言語の番号がidxで、それを話せる人が中身
es_p = [[] for _ in range(N+1)] # 各人の番号がidxで、その人の話せる言語が中身
for i in range(N):
    KL = list(map(int, input().split()))
    es_p[i+1].extend(KL[1:])
    for j in KL[1:]:
        es_lang[j].append(i+1)

checked_lang = [False] * (M+1)
checked_p = [False] * (N+1)

#人１からスタートする
stack_p = [1]
checked_p[1] = True
while len(stack_p) > 0:
    new_stack_p = [] # この次のループで調べる人の集合
    for p in stack_p:
        checked_p[p] = True
        stack_lang = []
        for lang in es_p[p]: #人ｐが話せる言語について調べる
            if checked_lang[lang] == False: # まだその言語を調査してないとき
                stack_lang.append(lang)
                checked_lang[lang] = True

        # 人pの持つ言語をだれが話せるか調べる
        for lang in stack_lang:
            for pp in es_lang[lang]: # 人ｐの話せる言語を話せる人について調べる
                if checked_p[pp] == False: # まだその人を調べてないなら次のループで調べる人に入れる
                    new_stack_p.append(pp)
                    checked_p[pp] = True

    if all(checked_p[1:]):
        print("YES")
        exit()
    if len(new_stack_p) > 0:
        stack_p = new_stack_p
    else:
        break



print("NO")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
K = [0] * N
L = [[] for _ in range(N + M)]
R = [i for i in range(N + M)]
def find(i):
  if R[i] == i:
    return i
  r = find(R[i])
  R[i] = r
  return r
def union(i, j):
  ri = find(i)
  rj = find(j)
  if ri > rj:
    R[ri] = rj
  else:
    R[rj] = ri
for i in range(N):
  _L = [int(x) + N - 1  for x in input().split()]
  for l in _L[1:]:
    union(i, l)
for i in range(N):
  find(i)
  if R[i]:
    print('NO')
    break
else:
  print('YES')