Problem:


Score : 400 points

Problem Statement

On a planet far, far away, M languages are spoken. They are conveniently numbered 1 through M.

For CODE FESTIVAL 20XX held on this planet, N participants gathered from all over the planet.

The i-th (1≦i≦N) participant can speak K_i languages numbered L_{i,1}, L_{i,2}, ..., L_{i,{}K_i}.

Two participants A and B can communicate with each other if and only if one of the following conditions is satisfied:

There exists a language that both A and B can speak.

There exists a participant X that both A and B can communicate with.

Determine whether all N participants can communicate with all other participants.

Constraints

2≦N≦10^5

1≦M≦10^5

1≦K_i≦M

(The sum of all K_i)≦10^5

1≦L_{i,j}≦M

L_{i,1}, L_{i,2}, ..., L_{i,{}K_i} are pairwise distinct.

Partial Score

200 points will be awarded for passing the test set satisfying the following: N≦1000, M≦1000 and (The sum of all K_i)≦1000.

Additional 200 points will be awarded for passing the test set without additional constraints.

Input

The input is given from Standard Input in the following format:

N M
K_1 L_{1,1} L_{1,2} ... L_{1,{}K_1}
K_2 L_{2,1} L_{2,2} ... L_{2,{}K_2}
:
K_N L_{N,1} L_{N,2} ... L_{N,{}K_N}

Output

If all N participants can communicate with all other participants, print YES. Otherwise, print NO.

Sample Input 1

4 6
3 1 2 3
2 4 2
2 4 6
1 6

Sample Output 1

YES

Any two participants can communicate with each other, as follows:

Participants 1 and 2: both can speak language 2.

Participants 2 and 3: both can speak language 4.

Participants 1 and 3: both can communicate with participant 2.

Participants 3 and 4: both can speak language 6.

Participants 2 and 4: both can communicate with participant 3.

Participants 1 and 4: both can communicate with participant 2.

Note that there can be languages spoken by no participant.

Sample Input 2

4 4
2 1 2
2 1 2
1 3
2 4 3

Sample Output 2

NO

For example, participants 1 and 3 cannot communicate with each other.



Sample input:
4 6
3 1 2 3
2 4 2
2 4 6
1 6


Sample output:
YES

Submission status: Accepted

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

# 連結成分の大きさを見るだけだった
# 言語と二部グラフを作る

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 += [x-1+N for x in L]

graph = csr_matrix(([1]*len(row), (row,col)), (N+M,N+M))

_,comp = connected_components(graph)

bl = (comp[:N] == comp[0]).all()

answer = 'YES' if bl else 'NO'
print(answer)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:
            x, y = y, x
        self.v[x] += self.v[y]
        self.v[y] = x

    def root(self, x):
        return self.v[x] < 0

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

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


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

uf = UnionFind(n + m)
for i in range(n):
    _, *lngs = map(int, input().split())
    for lng in lngs:
        uf.unite(i, n + lng - 1)

can = all(uf.same(j, n - 1) for j in range(n - 1))
print('YES' if can else 'NO')

Submission status: Accepted

Solution code:
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

n,m=map(int,input().split())
UF=UF(n+m)
for i in range(n):
  l=list(map(int,input().split()))
  for j in range(1,l[0]+1):
    UF.unite(i,n+l[j]-1)
ct=0
for i in range(n,n+m):
  if UF.size(i)==1:
    ct+=1
if UF.groupnum()-ct==1:
  print('YES')
else:
  print('NO')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
People = [[] for i in range(N)]
Language = [[] for i in range(M)]
for i in range(N):
    language = list(map(int, input().split()))[1:]
    for l in language:
        l -= 1
        People[i].append(l)
        Language[l].append(i)


people_visited = [False] * N
language_visited = [False] * M


stack = [(0, 'people')]
while stack:
    n, n_type = stack.pop()

    if n_type == 'people':
        people_visited[n] = True
        for to in People[n]:
            if language_visited[to]:
                continue
            stack.append((to, 'language'))

    elif n_type == 'language':
        language_visited[n] = True
        for to in Language[n]:
            if people_visited[to]:
                continue
            stack.append((to, 'people'))

print('YES' if all(people_visited) else 'NO')

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from functools import reduce

class UnionFind:
    def __init__(self, node: int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]

    def find(self, x: int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> bool:
        if self.isSame(x, y):
            # print("x and y has already united")
            return False

        rx = self.find(x)
        ry = self.find(y)

        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]

            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

        return True

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


n, m = li()
lang = [[] for _ in range(m)]
for person in range(n):
    kl = list(li_())
    for langi in kl[1:]:
        lang[langi].append(person)

uf = UnionFind(n)
for langi in lang:
    if len(langi) < 2:
        continue

    for i in range(len(langi)-1):
        uf.unite(langi[i], langi[i+1])


for i in range(n):
    uf.find(i)

ok = True
for i in range(1, n):
    if uf.isSame(0, i):
        continue

    else:
        ok = False
        break

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

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]
  
n,m=map(int,input().split())
t=UnionFind(n+m)
for i in range(n):
  l=list(map(int,input().split()))
  for j in range(l[0]):
    t.Unite(i+1,n+l[1+j])
s=set()
for i in range(n):
  r=t.FindRoot(i+1)
  s.add(r)
if len(s)==1:
  print('YES')
else:
  print('NO')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
from collections import defaultdict
root=[-1]*(N+M)
def find(i):
    global root
    if root[i]>=0:
        root[i]=find(root[i])
        return root[i]
    return i
def make(a,b):
    global root
    ra=find(a)
    rb=find(b)
    if ra==rb:
        return
    elif root[ra]<=root[rb]:
        root[ra]+=root[rb]
        root[rb]=ra
    else:
        root[rb]+=root[ra]
        root[ra]=rb
    return
for i in range(N):
    X=list(map(int,input().split()))
    for k in range(X[0]):
        make(i,N+X[k+1]-1)
r0=find(0)
flag=True
for i in range(1,N):
    if find(i)!=r0:
        flag=False
        break
if flag:
    print('YES')
else:
    print('NO')

Submission status: Accepted

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

e_list = [[] for i in range(N+M)]

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

vi = 0 #時と場合によってここを変える
from collections import deque
Q = deque([vi])
checked_list = [False]*(N+M)
checked_list[vi]=True
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.appendleft(v1)
flag=True
for i in range(N):
    if not checked_list[i]:
        flag=False

if flag:
    print("YES")
else:
    print("NO")

Submission status: Accepted

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

for k in range(N):
    P = list(map(int,input().split()))[1:]
    H.append(P)
    for e in P:
        L[e].append(k+1)

G = [0 for k in range(N+1)]
G[1] = 1
Q = [H[0]]
while len(Q) > 0:
    ima = Q.pop()
    for tsugi in ima:
        for e in L[tsugi]:
            if G[e] == 0:
                G[e] = 1
                if len(H[e-1]) > 1:
                    Q.append(H[e-1])

for k in range(1,N+1):
    if G[k] == 0:
        print("NO")
        exit(0)
print("YES")

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

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

class UnionFind():
    def __init__(self, N):
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        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 size(self, x):
        x = self.find(x)
        return self.counter[x]

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

uf = UnionFind(N+M)
for i in range(N):
    KL = list(map(int,input().split()))
    for L in KL[1:]:
        uf.unite(i,L+N-1)
ans = "YES"
for i in range(1,N):
    if not uf.same(0,i):
        ans = "NO"
print(ans)

Submission status: Accepted

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

parent = [i for i in range(N + M)]
rank = [0] * (N + M)


def find(i):
    if parent[i] == i:
        return i
    else:
        parent[i] = find(parent[i])
        return parent[i]


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


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


for i in range(N):
    P = list(map(int, input().split()))
    n = P[0]
    for j in range(1, n + 1):
        unite(i, P[j] - 1 + N)


k = find(0)
for i in range(N):
    if k != find(i):
        print('NO')
        exit()

print('YES')

Submission status: Accepted

Solution code:
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.size_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.size_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_

    def same(self, node):
        return self.root() == node.root()


N, M = map(int, input().split())
uf = [UnionFindNode(i) for i in range(M)]
l = []
for i in range(N):
    k, *lang = list(map(int, input().split()))
    for j in range(k - 1):
        uf[lang[j] - 1].unite(uf[lang[j + 1] - 1])
    l.append(lang)
r = uf[lang[0] - 1].root()
for i in range(N):
    if uf[l[i][0] - 1].root() != r:
        print('NO')
        exit(0)
print('YES')

Submission status: Accepted

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

L=[]

for i in range(N):
    S=list(map(int,input().split()))
    del S[0]
    L.append(S)
#print(L)

P=[i for i in range(m+1)]
size=[1 for i in range(m+1)]

def find(x):
    if P[x]==x:
        return x
    else:
        return find(P[x])
        
def union(y,z):
    Y=find(y)
    Z=find(z)
    if size[Y]>=size[Z]:
        size[Y]+=size[Z]
        P[Z]=P[Y]
    else:
        size[Z]+=size[Y]
        P[Y]=P[Z]
        
for i in range(len(L)):
    if len(L[i])>=2:
        for j in range(1,len(L[i])):
            if find(L[i][j-1])==find(L[i][j]):
                pass
            else:
                union(L[i][j-1],L[i][j])
#print(P)
F=[0 for i in range(m+1)]
for i in range(len(L)):
    for j in range(len(L[i])):
        F[L[i][j]]=1
#print(F)

cnt=0
for i in range(len(F)):
    if F[i]==1 and P[i]==i:
        cnt+=1
if cnt==1:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
a=[[]for i in range(n+m)]
for i in range(n):
    s=list(map(int,input().split()))
    for j in s[1:]:
        a[i].append(j+n-1)
        a[n+j-1].append(i)
t=[False]*(n+m)
def g(x):
    t[x]=True
    for i in a[x]:
            if not t[i]:
                g(i)
g(0)
if all(t[:n]):
    print("YES")
else:
    print("NO")

Submission status: Accepted

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

def dfs(v):
    used[v] = True
    for _v in adjl[v]:
        if not used[_v]:
            dfs(_v)

n, m = map(int, input().split())
adjl = [[] for v in range(n + m)]
for i in range(n):
    kl = list(map(int, input().split()))
    k = kl[0]
    llist = kl[1:]
    for l in llist:
        adjl[i].append(l + n - 1)
        adjl[l + n - 1].append(i)

used = [False] * (n + m)
dfs(0)

if all(used[:n]):
  print('YES')
else:
  print('NO')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
from collections import defaultdict
lang=[-1]*(M+1)
data=defaultdict(int)
def search(l):
    if lang[l]>=0:
        lang[l]=search(lang[l])
    elif lang[l]<0:
        return l
    return lang[l]
def union(i,j,lang):
    iidx=search(i)
    jidx=search(j)
    if iidx==jidx:
        return lang
    elif lang[iidx]<=lang[jidx]:
        lang[iidx]+=lang[jidx]
        lang[jidx]=iidx
    else:
        lang[jidx]+=lang[iidx]
        lang[iidx]=jidx
    return lang
for i in range(N):
    line=list(map(int,input().split()))
    data[line[1]]+=1
    for k in range(1,line[0]):
        data[line[k+1]]+=1
        lang=union(line[k],line[k+1],lang)
L=set()
for k in range(1,1+M):
    if data[k]==0:continue
    L|={search(k)}
if len(L)>1:
    print('NO')
elif len(L)==1:
    print('YES')

Submission status: Accepted

Solution code:
def init(n):
    global par, rank
    par = [i for i in range(n)]
    rank = [0] * n

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

def unite(x, y):
    global par, rank
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

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

N, M = map(int, input().split())
init(N + M)
for i in range(N):
    a = list(map(int, input().split()))
    for L in a[1:]:
        unite(i, L - 1 + N)
ans = "YES"
for i in range(N):
    if not same(0, i):
        ans = "NO"
        break
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, x):
        self.__par = list(range(x))
        self.__rank = [0] * x

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.__rank[x] > self.__rank[y]:
            self.__par[y] = x
        else:
            self.__par[x] = y
            if self.__rank[x] == self.__rank[y]:
                self.__rank[y] += 1

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


if __name__ == '__main__':
    n, m = map(int, input().split())
    uf = UnionFind(n + m)

    for i in range(n):
        for l in (int(s) + n - 1 for s in input().split()[1:]):
            uf.unite(i, l)

    print('YES' if all(uf.same(0, v) for v in range(1, n)) else 'NO')

Submission status: Accepted

Solution code:
import sys
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納　par[x] == x の時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0)
        self.rank = [0] * (n+1)
        # 各々の集合の要素数（根が代表して値を持っておく）
        self.count = [1] * (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
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            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 size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]

N,M=map(int,input().split())
K=[set() for i in range(M)]
tree=UnionFind(N)
for i in range(N):
    L=[int(i)-1 for i in input().split()]
    for m in L[1:]:
        K[m].add(i)
for i in range(M):
    Ki=list(K[i])
    if len(Ki)==0:
        continue
    for h in range(len(Ki)):
        tree.union(Ki[h],Ki[0])
for i in range(N):
    if not tree.same_check(0,i):
        print('NO')
        sys.exit()
print('YES')

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)
        self.size = [1] * (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]:
            if self.same_check(x, y) != True:
                self.size[y] += self.size[x]
                self.size[x] = 0
            self.par[x] = y
        else:
            if self.same_check(x, y) != True:
               self.size[x] += self.size[y]
               self.size[y] = 0
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
               self.rank[x] += 1

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


N, M = list(map(int, input().split()))
l = [[] for i in range(M)]
uf = UnionFind(N)

for i in range(N):
    kl = list(map(int, input().split()))
    K = kl[0]
    for j in range(1, K + 1):
        l[kl[j] - 1].append(i + 1)

for i in range(M):
    for j in range(len(l[i]) - 1):
        uf.union(l[i][0], l[i][1 + j])

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
p_lgngs=[[]for _ in range(N)]
l_peops=[[]for _ in  range(M+1)]
n_isl=0
lset=set()

data=[-1]*(M+1)
rank=[1 ]*(M+1)
def find(x):
  while data[x]!=-1: 
    x=data[x]
  return x
def unite(a,b):
  a,b=find(a),find(b)
  if a!=b:
    if  rank[a]<rank[b]:
      a,b=b,a
    if rank[a]==rank[b]:
      rank[a]+=1
    data[b]=a
    return True
  else: 
    return False
    
for i in range(N):
  k,*L=list(map(int,input().split()))
  p_lgngs[i]+=L
  for ll in L:
    l_peops[ll].append(i)
    lset.add(ll)
  for q in range(1,k):
    if unite(L[q-1], L[q]):
      n_isl-=1
if n_isl+len(lset)==1:
  print("YES")
else:
  print("NO")
exit(0)
print(n_isl+len(lset))
#print(lset)
#print(data)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]

    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return

        if x<y:
            self.par[y] = x
        else:
            self.par[x] = y

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


n,m = map(int, input().split())
uf = UnionFind(n+m)

for u in range(n):
    line = list(map(int, input().split()))
    k = line[0]
    for l in line[1:]:
        lng = n+l-1
        uf.unite(u, lng)

flag = True
for u in range(1,n):
    if not uf.same(0,u):
        flag = False
        break
if flag:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = [-1]*m
def root(a):
    if l[a] < 0:return a
    l[a] = root(l[a])
    return l[a]
def unite(a,b):
    ra, rb = root(a), root(b)
    if ra == rb:
        return
    if l[ra] > l[rb]:
        ra, rb = rb, ra
    l[ra] += l[rb]
    l[rb] = ra

d = set()
for i in range(n):
    _, *k = list(map(int, input().split()))
    from_ = k[0]-1
    if from_ not in d:
        d.add(from_)
    for j in range(1,len(k)):
        unite(from_, k[j]-1)
        if k[j]-1 not in d:
            d.add(k[j]-1)

if sum(l[i] < 0 for i in d) > 1:
    print("NO")
else:
    print("YES")

Submission status: Accepted

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

def dfs(vNow):
    useds[vNow] = True
    for v2 in adjL[vNow]:
        if not useds[v2]:
            dfs(v2)

N, M = map(int, input().split())
adjL = [[] for v in range(N+M)]
for i in range(N):
    K, *Ls = map(int, input().split())
    for L in Ls:
        adjL[i].append(L+N-1)
        adjL[L+N-1].append(i)

useds = [False] * (N+M)
dfs(0)

print('YES' if all(useds[:N]) else 'NO')

Submission status: Accepted

Solution code:
# Union-Findデータ構造
class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def find(self, x):
        if self.pars[x] == x: return x
        else:
            self.pars[x] = self.find(self.pars[x])
            return self.pars[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)

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

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
kl = []
for i in range(n):#h:高さ
    kl.append([int(m) for m in input().split()])
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 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

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

u = UnionFind(n + m)
for i in range(n):
    ki = kl[i][0]
    for j in range(1, ki + 1):
        u.union(m + i + 1, kl[i][j])
print(('NO', 'YES')[all(u.same_check(m + 1, m + i + 1) for i in range(n))])

Submission status: Accepted

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

N, M = map(int, input().split())
P_to_L = [[] for i in range(N)]  # 人から言語へのグラフ
L_to_P = [[] for i in range(M)]  # 言語から人へのグラフ

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


P_visited = [False] * N  # 訪問済み人
L_visited = [False] * M  # 訪問済み言語


def dfs(n, p_to_l):
    if p_to_l:
        P_visited[n] = True
        for to in P_to_L[n]:
            if not L_visited[to]:
                dfs(to, False)
    else:
        L_visited[n] = True
        for to in L_to_P[n]:
            if not P_visited[to]:
                dfs(to, True)


dfs(0, True)
print('YES' if all(P_visited) else 'NO')

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,size):
        self.table=[-1for _ in range(size)]
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]!=self.table[s2]:
                if self.table[s1]<self.table[s2]:
                    self.table[s2]=s1
                else:
                    self.table[s1]=s2
            else:
                self.table[s1]+=-1
                self.table[s2]=s1
        return
    def same(self,x,y):
      return self.root(x)==self.root(y)
n,m=map(int,input().split())
UF=UnionFind(n+m)
for i in range(n):
    for t in map(int,input().split()[1:]):
        UF.unite(i,n+t-1)
print('YNEOS'[len(set(UF.root(i)for i in range(n)))>1::2])

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

  
n,m = (int(i) for i in input().split())
k = []
uf = UnionFind(m)
for i in range(n):
  a = []
  a = list(int(i) for i in input().split())
  a.pop(0)
  k.append(a)
for i in k:
  tmp = i[0]
 #言語ごとに同じ人がいたらunion
  for j in i[1:]:
   uf.union(tmp,j)
    
 #任意の二人が同じunionに属するか？
b = uf.find(k[0][0])
for k in k[1:]:
  if b == uf.find(k[0]):
    continue 
  else:
    print('NO')
    exit()
print('YES')

Submission status: Accepted

Solution code:
import sys


class Unionfindtree:
    def __init__(self, number):
        self.par = [i for i in range(number)]
        self.rank = [0] * (number)

    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,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.par[px] = py
        else:
            self.par[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

    def connect(self, x, y):  # 親が同じかみる
        return self.find(x) == self.find(y)


N,M=map(int,input().split())
K=[set() for i in range(M)]
tree=Unionfindtree(N)
for i in range(N):
    L=[int(i)-1 for i in input().split()]
    for m in L[1:]:
        K[m].add(i)
for i in range(M):
    Ki=list(K[i])
    if len(Ki)==0:
        continue
    for h in range(len(Ki)):
        tree.union(Ki[h],Ki[0])
for i in range(N):
    if not tree.connect(0,i):
        print('NO')
        sys.exit()
print('YES')