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:
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0 for _ in range(n + 1)]
        self.size = [1] * (n + 1)

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

    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.parent[x] = y
            self.size[y] += self.size[x]

        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.size[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_size(self, x):
        return self.size(self.find(x))


N, M = map(int, input().split())
lang_list = []
k_list = []
for i in range(N):
    tmp = tuple(map(int, input().split()))
    k_list.append(tmp[0])
    lang_list.append(tmp[1:])
union_find = UnionFind(M)

for lang in lang_list:
    tmp = lang[0]
    for l in lang[1:]:
        union_find.union(tmp, l)

p = union_find.find(lang_list[0][0])
for lang in lang_list[1:]:
    if p == union_find.find(lang[0]):
        continue
    else:
        print("NO")
        exit()
print("YES")

Submission status: Accepted

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

UF = list(range(M + 1))


def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]


def unite(a, x, y):
    X = find(a, x)
    Y = find(a, y)
    Z = min(X, Y)
    a[X], a[Y] = Z, Z


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


for kl in KL:
    K, L = kl[0], kl[1:]
    for i in range(K - 1):
        unite(UF, L[i], L[i + 1])
for kl in KL:
    if not same(UF, KL[0][1], kl[1]):
        print('NO')
        exit()
print('YES')

Submission status: Accepted

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
    
    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
            if self.par[rx] > self.par[ry]:
                self.par[rx] = ry
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
        return
    
lang = defaultdict(lambda: [])
N, M = inpl()
for i in range(N):
    L = inpl()[1:]
    for j in L:
        lang[j].append(i)
CF = UnionFind(N)
for Li in lang.values():
    t = Li[0]
    for j in Li:
        CF.union(t, j)
uni = [i for i in CF.par if i< 0]
if len(uni) == 1:
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
L=[[] for i in range(M)]
for i in range(N):
  for j,k in enumerate(input().split()):
    if j==0:
      continue
    L[int(k)-1].append(i)
G=[[] for i in range(N)]
for l in L:
  if len(l)>=2:
    for i in range(len(l)-1):
      if l[i+1] not in G[l[i]]:
        G[l[i]].append(l[i+1])
        G[l[i+1]].append(l[i])

V=[False]*N
n=1
dfs_stack=deque([0])
while dfs_stack:
  a=dfs_stack.popleft()
  if not V[a]:
    n+=1
    for b in G[a]:
      if not V[b]:
        dfs_stack.append(b)
  V[a]=True
if V==[True]*N:
  print("YES")
else:
  print("NO")

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
EN, EM = [[] for i in range(N)], [[] for i in range(M)]
for i in range(N):
    IP = [int(k) for k in input().split()]
    EN[i] = [a-1 for a in IP[1:]]
    for j in IP[1:]:
        EM[j-1].append(i)

VN, VM = [False for i in range(N)], [False for i in range(M)]
Q = deque()
Q.append(0)
VN[0] = True
while Q:
    tempN = Q.popleft()
    VN[tempN] = True
    for m in EN[tempN]:
        if not VM[m]:
            VM[m] = True
            for n in EM[m]:
                if not VN[n]:
                    VN[n] = True
                    Q.append(n)

if False in VN: print("NO")
else: print("YES")

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
L=[]
for i in range(N):
    L.append([int(i)-1 for i in input().split()][1:])
K=[len(L[i]) for i in range(N)]
X=[-1 for i in range(M)]
for i in range(N):
    for j in range(K[i]):
        if X[L[i][j]]==-1:
            X[L[i][j]]=i
par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        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
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)
init(N)
for i in range(N):
    for j in range(K[i]):
        unite(i,X[L[i][j]])
for i in range(1,N):
    if not(same(0,i)):
        print("NO")
        exit()
print("YES")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


class UnionFind:
    def __init__(self, N):
        # type: (int) -> None
        self.N = N
        self.parent = list(range(N))  # type: List[int]

    def root(self, x):
        # type: (int) -> int
        path_to_root = []
        while self.parent[x] != x:
            path_to_root.append(x)
            x = self.parent[x]
        for node in path_to_root:
            self.parent[node] = x  # パス圧縮
        return x

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

    def unite(self, x, y):
        # type: (int, int) -> None
        self.parent[self.root(x)] = self.root(y)

    def __str__(self):
        # type: () -> str
        groups = {}  # type: Dict[int, List[int]]
        for x in range(self.N):
            root = self.root(x)
            if root in groups.keys():
                groups[root].append(x)
            else:
                groups[root] = [x]
        result = ""
        for root in groups.keys():
            result += str(groups[root]) + "\n"
        return result

    def __len__(self):
        # type: () -> int
        roots = list(map(lambda x: self.root(x),
                         range(self.N)))
        return len(set(roots))


N, M = map(int, input().split())
K = []
L = []
for i in range(N):
    temp = list(map(int, input().split()))
    K.append(temp[0])
    L.append(list(map(lambda x: x-1,
                      temp[1:])))


speaker = [[] for i in range(M)]  # type: List[List[int]]


for i in range(N):
    for k in range(K[i]):
        speaker[L[i][k]].append(i)

u = UnionFind(N)
for l in range(M):
    sp = speaker[l]
    if len(sp) > 0:
        for i in range(1, len(sp)):
            u.unite(sp[0], sp[i])
if len(u) == 1:
    print("YES")
else:
    print("NO")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
parent = [i for i in range(N + M)]
rank = [1] * (N + M)
def find(x):
    if x == parent[x]:
        return x
    parent[x] = find(parent[x])
    return parent[x]

def unite(x, y):
    x, y = find(x), find(y)
    if x == y:
        return
    if rank[x] == rank[y]:
        rank[x] += 1
    elif rank[x] < rank[y]:
        x, y = y, x
    parent[y] = x
for i in range(N):
    for l in list(map(int, input().split()))[1:]:
        # 言語はparentの後半
        unite(i, N + l - 1)
if all(find(0) == find(i) for i in range(N)):
    print('YES')
else:
    print('NO')

Submission status: Accepted

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

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

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

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
		return

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

uf = UnionFind(n)
for i in range(m):
	if len(lang[i]) <= 1:
		continue
	else:
		for j in range(len(lang[i]) - 1):
			uf.union(lang[i][j], lang[i][j + 1])

root_count = 0
for i in range(n):
	if uf.table[i] < 0:
		root_count += 1

if root_count == 1:
	print("YES")
else:
	print("NO")

Submission status: Accepted

Solution code:
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

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)

from collections import defaultdict

dic = defaultdict(list)

n,m = li()

# 各言語を話せる人を登録
for i in range(n):
    l_list = li()
    for l in l_list[1:]:
        dic[l].append(i)
        
# union-findでマージしていく
uf = UnionFind(n)
for key in dic.keys():
    val = dic[key]
    for i in range(len(val)-1):
        if not uf.isSame(val[i], val[i+1]):
            uf.unite(val[i], val[i+1])
            
root = uf.find(0)
for i in range(n):
    if uf.find(i) != root:
        print("NO")
        break
    
    if i == n-1:
        print("YES")

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

def Find(x):	#xの根を返す
	global table

	if table[x] == x:
		return x
	else:
		table[x] = Find(table[x])	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def Unite(x,y):	#xとyを繋げる
	x = Find(x)
	y = Find(y)

	if x == y:
		return

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

def Check(x,y):
	if Find(x) == Find(y):
		return True
	else:
		return False

N,M = inpl()

table = [i for i in range(N+M)]	#木の親 table[x] == x なら根
rank  = [1 for i in range(N+M)]	#木の長さ

for i in range(N):
	tmp = inpl()
	for k in range(tmp[0]):
		l = tmp[k+1]
		Unite(i,l+N-1)

tmp = Find(0)
for i in range(N):
	if tmp != Find(i):
		print('NO')
		sys.exit()
print('YES')

Submission status: Accepted

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

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

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(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
#-----------------------------------------------------
n,m = map(int,raw_input().split())

uf = UnionFind(n+m)

for i in xrange(n):
	langs = map(int,raw_input().split())
	for j in xrange(1,langs[0] + 1):

		uf.union(i,langs[j]+n-1)

a = uf.find(0)

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

	if uf.find(i) != a:
		print 'NO'
		quit()

print 'YES'

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
G = [[] for i in range(N+M)]
check = [0 for j in range(N+M)]


def bfs(s):
    q = deque()
    check[s] = 1
    q.append(s)

    while len(q) != 0:
        u = q.popleft()
        for v in G[u]:
            if check[v] == 0:
                check[v] = 1
                q.append(v)

        check[u] = 2


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

    bfs(0)

    for i in range(N):
        if check[i] == 0:
            print("NO")
            break
    else:
        print("YES")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

P_visited = [0] * N
L_visited = [0] * M


# flgが立っていれば、人を見ているとする
def dfs(n, flg):
    if flg:
        P_visited[n] = 1
        for l in P[n]:
            if not L_visited[l]:
                dfs(l, flg ^ 1)
    else:
        L_visited[n] = 1
        for p in L[n]:
            if not P_visited[p]:
                dfs(p, flg ^ 1)


dfs(0, 1)
print("YES" if all(P_visited) else "NO")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2 * 10**5)
N,M = map(int,input().split())

par = [i for i in range(N+M)]
def root(a):
    if par[a] == a: return a
    par[a] = root(par[a])
    return par[a]

def same(a,b):
    return root(a) == root(b)

def unite(a,b):
   ra,rb = root(a),root(b)
   if ra == rb: return
   par[ra] = rb

for i in range(N):
    src = list(map(lambda x:int(x)-1,input().split()))
    if len(src) == 1: continue
    for j in src[1:]:
        unite(i,N+j)

for i in range(1,N):
    if not same(0,i):
        print('NO')
        exit()
print('YES')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class unionfind:
    def __init__(self, n):
        self.parent = [-1] * n
    def find(self, x):
        if self.parent[x] < 0:
            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.parent[x] > self.parent[y]: x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
    def issame(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):
    L = [int(x) - 1 for x in input().split()]
    for j in range(L[0] + 1):
        uf.unite(L[j + 1], M + i)
print(('NO', 'YES')[all(uf.issame(M, M + i) for i in range(N))])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class UnionFind():
    def __init__(self, size):
        self.table = [-1] * size

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

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


N, M = map(int, input().split())
uf = UnionFind(N + M)
for i in range(N):
    L = [int(x) - 1 for x in input().split()]
    L[0] += 1
    for j in range(L[0]):
        uf.union(L[j + 1], M + i)

ans = True
for i in range(N):
    if uf.find(M + i) != uf.find(M):
        ans = False
print(('NO', 'YES')[ans])

Submission status: Accepted

Solution code:
from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))

def find(x):
    if par[x] == x:
        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
    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 = readLine_int_list()
v = n + m
par = [i for i in range(0, v)]
rank = [1] * v
def main():
    for i in range(n):
        for ii in readLine_int_list()[1:]:
           unite(i, ii-1+n)
           
    r = "YES"
    for i in range(0, n):
        if find(i) != find(0):
            r = "NO"
    print(r)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
q,w,e=input,range,int
n,m=map(e,q().split())
V=n+m
p,s=[i for i in w(V)],[1]*V
def f(x):
    if x==p[x]:
        return x
    p[x]=f(p[x]);return p[x]


def u(x, y):
    x, y = f(x), f(y)
    if x==y:
        return
    if s[x] < s[y]:
        x, y = y, x
    p[y] = x
    s[x] += s[y]


[u(i,l-1+n)for i in w(n)for l in [e(k)for k in q().split()][1:]]
print("NO"if len([i for i in w(n)if f(i)!=f(0)])>0 else"YES")

Submission status: Accepted

Solution code:
q,w,e=input,range,int
n,m=map(e,q().split())
V=n+m
par,sizes=[i for i in w(V)],[1]*V


def f(x):
    if x == par[x]:
        return x
    par[x] = f(par[x])
    return par[x]


def u(x, y):
    x, y = f(x), f(y)
    if x == y:
        return
    if sizes[x] < sizes[y]:
        x, y = y, x
    par[y] = x
    sizes[x] += sizes[y]


[u(i,l-1+n)for i in w(n)for l in [e(k)for k in q().split()][1:]]
print("NO"if len([i for i in w(n)if f(i)!=f(0)])>0 else"YES")

Submission status: Accepted

Solution code:
q,w,e=input,range,int

n, m = map(e,q().split())
V = n + m
par = [i for i in w(V)]
sizes = [1] * V


def f(x):
    if x == par[x]:
        return x
    par[x] = f(par[x])
    return par[x]


def u(x, y):
    x, y = f(x), f(y)
    if x == y:
        return
    if sizes[x] < sizes[y]:
        x, y = y, x
    par[y] = x
    sizes[x] += sizes[y]


[u(i,l-1+n)for i in w(n)for l in [e(k)for k in q().split()][1:]]
print("NO"if len([i for i in w(n)if f(i)!=f(0)])>0 else"YES")

Submission status: Accepted

Solution code:
q=input
w=range
n, m = map(int, q().split())
V = n + m
par = [i for i in w(V)]
sizes = [1] * V


def f(x):
    if x == par[x]:
        return x
    par[x] = f(par[x])
    return par[x]


def u(x, y):
    x, y = f(x), f(y)
    if x == y:
        return
    if sizes[x] < sizes[y]:
        x, y = y, x
    par[y] = x
    sizes[x] += sizes[y]


[u(i,l-1+n)for i in w(n)for l in [int(k)for k in q().split()][1:]]
print("NO"if len([i for i in w(n)if f(i)!=f(0)])>0 else"YES")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
V = n + m
par = [i for i in range(V)]
sizes = [1] * V


def f(x):
    if x == par[x]:
        return x
    par[x] = f(par[x])
    return par[x]


def unite(x, y):
    x, y = f(x), f(y)
    if x == y:
        return
    if sizes[x] < sizes[y]:
        x, y = y, x
    par[y] = x
    sizes[x] += sizes[y]


[unite(i,l-1+n)for i in range(n)for l in [int(k)for k in input().split()][1:]]
print("NO"if len([i for i in range(n)if f(i)!=f(0)])>0 else"YES")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
V = n + m
par = [i for i in range(V)]
sizes = [1] * V


def f(x):
    if x == par[x]:
        return x
    par[x] = f(par[x])
    return par[x]


def unite(x, y):
    x, y = f(x), f(y)
    if x == y:
        return
    if sizes[x] < sizes[y]:
        x, y = y, x
    par[y] = x
    sizes[x] += sizes[y]


for i in range(n):
    for l in [int(k)for k in input().split()][1:]:
        unite(i,l-1+n)
print("NO"if len([i for i in range(n)if f(i)!=f(0)])>0 else"YES")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
V = n + m
par = [i for i in range(0, V)]
sizes = [1] * V


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


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if sizes[x] < sizes[y]:
        x, y = y, x
    par[y] = x
    sizes[x] += sizes[y]


for i in range(0, n):
    for l in [int(k)for k in input().split()][1:]:
        unite(i, l - 1 + n)
print("NO" if len([i for i in range(0, n)if find(i) != find(0)]) > 0 else "YES")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
V = n + m
par = [i for i in range(0, V)]
sizes = [1] * V


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


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if sizes[x] < sizes[y]:
        x, y = y, x
    par[y] = x
    sizes[x] += sizes[y]


for i in range(0, n):
    for l in [int(k)for k in input().split()][1:]:
        unite(i, l - 1 + n)
r = "YES"
if len([i for i in range(0, n)if find(i) != find(0)]) > 0:
    r = "NO"
print(r)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
V = n + m
par = [i for i in range(0, V)]
sizes = [1] * V


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


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if sizes[x] < sizes[y]:
        x, y = y, x
    par[y] = x
    sizes[x] += sizes[y]


for i in range(0, n):
    for l in [int(k)for k in input().split()][1:]:
        unite(i, l - 1 + n)
r = "YES"
for i in range(0, n):
    if find(i) != find(0):
        r = "NO"
print(r)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def f():
    n,m = list(map(int, input().split()))
    a = list(range(m+1))
    g = [False]*(m+1)
    uf = UnionFind(m+1)
    mi = None
    for _ in range(n):
        c = list(map(int, input().split()))
        if not mi:
            mi = c[1]
        g[c[1]] = True
        if c[0] > 1:
            for i in range(c[0]-1):
                g[c[2+i]] = True
                uf.union(c[1], c[2+i])

    t = uf.find(mi)

    for i in range(m+1):
        if not g[i]:
            continue
        if uf.find(i) != t:
            return 'NO'
    return 'YES'



print(f())

Submission status: Accepted

Solution code:
import sys

next(sys.stdin)

_, *langs = map(int, next(sys.stdin).strip().split())
common_langs = set(langs)

unreachable = list()
for line in sys.stdin:
    _, *langs = map(int, line.strip().split())
    unreachable.append(set(langs))

change = True
while change:
    change = False
    for langs in unreachable:
        if len(common_langs & langs) > 0:
            s = len(common_langs)
            common_langs.update(langs)
            change |= not s == len(common_langs)
            langs.clear()
    unreachable = list(langs for langs in unreachable if len(langs) > 0)

if len(unreachable) == 0:
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, raw_input().split())
G = dict()
for n in range(N):
    L = map(int, raw_input().split())
    # Agent
    G['A'+str(n+1)] = {'con':False, 'edge':map(str, L[1:])}
    for l in L[1:]:
        if G.has_key(str(l)) == False:
            G[str(l)] = {'con':False, 'edge':['A'+str(n+1)]}
        else:
            G[str(l)]['edge'].append('A'+str(n+1))


queue = deque(['A1'])
G['A1']['con'] = True

while len(queue) > 0:
    q = queue.popleft()
    for p in G[q]['edge']:
        if G[p]['con']:
            pass
        else:
            G[p]['con'] = True
            queue.append(p)
res = 'YES'
for n in range(N):
    if G['A'+str(n+1)]['con'] == False:
        res = 'NO'
        break
print res

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

class UnionFind:
    def __init__(self, size):
        self.rank = [0] * size
        self.par = range(size)
        self.g_num = size

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

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

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

        self.g_num -= 1
        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 group_num(self):
        return self.g_num

N, M = map(int, raw_input().split())
L = [map(int, raw_input().split()) for i in xrange(N)]

sp = [-1]*M
uf = UnionFind(N)
for i in xrange(N):
    k = L[i][0]
    for j in xrange(1, k + 1):
        if sp[L[i][j] - 1] == -1:
            sp[L[i][j] - 1] = i
        else:
            uf.unite(sp[L[i][j] - 1], i)

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,size):
        self.parent=range(size)
        self.tree_num=size
        self.tree_w=[1]*size
        self.rank=[0]*size

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

    def unite(self,x,y):
        x=self.findset(x)
        y=self.findset(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.parent[x]=y
            self.tree_num-=1
            self.tree_w[y]+=self.tree_w[x]
        else:
            self.parent[y]=x
            self.tree_num-=1
            self.tree_w[x]+=self.tree_w[y]
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

    def same(self,x,y):
        if self.findset(x)==self.findset(y):
            return True
        else:
            return False

    def tree_number(self):
        return self.tree_num

    def tree_weight(self,x):
        return self.tree_w[self.findset(x)]

n,m=map(int,raw_input().split())
p=[map(int,raw_input().split()) for _ in xrange(n)]
g=[[] for _ in xrange(m)]
for i in xrange(n):
    for j in p[i][1:]:
        g[j-1].append(i)
uf=UnionFind(n)
for i in xrange(m):
    for j in xrange(len(g[i])):
        uf.unite(g[i][0],g[i][j])
if uf.tree_number()==1:
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

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])
ans = "YES"
for e, *_ in l:
    e -= 1
    if uf.find_set(e) != p:
        ans = "NO"

print(ans)