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.

Solution (Python):
import sys
input = sys.stdin.readline


class UnionFindTree():
    def __init__(self, N):
        self.N = N
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, a):
        return self.__size[self.root(a)]

    def groups(self):
        groups = {}
        for k in range(self.N):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, M = map(int, input().split())
    uft = UnionFindTree(N)
    speakers = [[] for _ in range(M)]
    for i in range(N):
        langs = list(map(int, input().split()))
        for l in langs[1:]:
            speakers[l-1].append(i)
    for i in range(M):
        for j in range(1, len(speakers[i])):
            uft.unite(speakers[i][j-1], speakers[i][j])
    if len(uft.groups()) == 1:
        print("YES")
    else:
        print("NO")


if __name__ == "__main__":
    main()

Solution (Python):
N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N ]

E = [[[] for _ in [0]*N] , [[] for _ in [0]*M]]
for i,kl in enumerate(KL):
    for l in kl[1:]:
        E[0][i].append(l-1)
        E[1][l-1].append(i)

Check = [[False]*N,[False]*M]
Check[0][0] = True
q = [[0,0]]
while q:
    cl,i = q.pop()
    for j in E[cl][i]:
        if Check[1-cl][j]:continue
        q.append([1-cl,j])
        Check[1-cl][j] = True

if sum(Check[0]) == N:
    print("YES")
else:
    print("NO")

Solution (Python):
import sys
input = sys.stdin.readline


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 size(self, x):
        return -self.root[self.find_root(x)]


N, M = map(int, input().split())
lang = [[] for _ in range(M+1)]
for i in range(N):
    lang_list = list(map(int, input().split()))
    for j in range(1, len(lang_list)):
        lang[lang_list[j]].append(i)

UF = UnionFind(N)
for speaker in lang:
    for i in range(1, len(speaker)):
        UF.unite(speaker[0], speaker[i])

if UF.size(0) == N:
    print('YES')
else:
    print('NO')

Solution (Python):
class UnionFind:
    
    def __init__(self, n):
        
        self.par = [-1] * n
        
        self.rank = [0] * n

    
    def find(self, x):
        if self.par[x] < 0:
            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:
            
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            
            self.par[x] += self.par[y]
            self.par[y] = x

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

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


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

u = UnionFind(len(l))
for i in range(len(l)):
    for j in range(len(l[i])):
        u.unite(i,l[i][j])

for i in range(n):
    if not u.same(0,i):
        print('NO')
        exit()
print('YES')

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range((n+m))]
for i in range(n):
    a=[int(i)-1 for i in input().split()][1:]
    for l in a:
        g[i].append(n+l)
        g[n+l].append(i)

par=[i for i in range(n+m)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
        
def connect(x,y):
    rx=root(x)
    ry=root(y)
    if rx!=ry:
        par[rx]=ry
    return

for i in range(n+m):
    for nb in g[i]:
        connect(i,nb)

p=par[0]
ans='YES'
for i in range(n):
    if par[i]!=p:
        ans='NO'

print(ans)

Solution (Python):
n, m = [int(item) for item in input().split()]
query = []
appeared = set()
for i in range(n):
    line = [int(item) for item in input().split()]
    appeared.update(line[1:])
    query.append(line[1:])
    
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1] * n
        self.rank = [0] * 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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        return self.size[self.find(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

uf = UnionFind(m)
for q in query:
    if len(q) == 1:
        continue
    for item in q[1:]:
        if not uf.same_check(q[0]-1, item-1):
            uf.union(q[0]-1, item-1)
    
par = uf.find(appeared.pop() - 1)
for item in appeared:
    if uf.find(item - 1) != par:
        print("NO")
        exit()
print("YES")

Solution (Python):
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)
ass = set()
N,K=map(int,input().split())
uni = UnionFind(K-1)
for _ in range(N):
    t = list(map(int,input().split()))
    ass.add(t[1]-1)
    if t[0] !=1:
        for k in t[2:]:
            uni.union(t[1]-1,k-1)
            ass.add(k-1)
            
p = set()
for i in ass:
    d = uni.find(i)
    p.add(d)
print("YES" if 1 ==len(p) else "NO")

Solution (Python):
N, M = map(int, input().split())
X = [i for i in range(M)]
Y = [0] * M
def par(i):
    if X[i] == i:
        return i
    t = par(X[i])
    X[i] = t
    return t
c = 0
for _ in range(N):
    Z = [int(a) - 1 for a in input().split()][1:]
    i = Z[0]
    for j in Z:
        if Y[j] == 0:
            c += 1
            Y[j] = 1
        pi = par(i)
        pj = par(j)
        if pi != pj:
            X[pj] = pi
            c -= 1
if c == 1:
    print("YES")
else:
    print("NO")

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

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

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

    def merge(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 get_size(self, x):
        x = self.find(x)
        return -self.v[x]


n, m = map(int, input().split())
e = []

uf = UnionFind(n + m)
for i in range(n):
    k, *l = map(int, input().split())
    l = tuple(map(lambda x: x - 1, l))
    e.append(l)

for i, lang_lst in enumerate(e):
    for lg in lang_lst:
        uf.merge(i, n + lg)

root = uf.find(0)
print('YES' if all(uf.find(i) == root for i in range(1, n)) else 'NO')

Solution (Python):
n,m = (int(i) for i in input().split())
par,rank,ans = [i for i in range(m+n)],[0 for i in range(m+n)],"YES"
def root(x):
	if par[x]!=x: par[x] = root(par[x])
	return par[x]
def unite(x,y):
	x2,y2 = root(x),root(y)
	if x2!=y2:
		if rank[x2]<rank[y2]: par[x2] = y2
		else: par[y2] = x2
		if rank[x2]==rank[y2]: rank[x2]+=1
def same(x,y):
	return root(x)==root(y)
for i in range(n):
    y = [int(k)-1 for k in input().split()]
    for j in y[1:]: unite(j,m+i)
for i in range(1,n):
    if not same(m,m+i): ans = "NO"
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7


class UnionFind:
    def __init__(self, n):
        self.n = n
        
        
        self.par = [i for i in range(n+1)]
        
        self.rank = [0] * (n+1)
        
        self.size = [1] * (n+1)
        
        self.tree = [True] * (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 x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

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

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

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

    
    def is_tree(self, x):
        return self.tree[self.find(x)]
    
    
    def len(self):
        res = set()
        for i in range(self.n+1):
            res.add(self.find(i))
        
        return len(res) - 1


N,M=MAP()


lang=[[] for i in range(M+1)]
for i in range(N):
    for j in LIST()[1:]:
        lang[j].append(i+1)

uf=UnionFind(N)
for i in range(1, M+1):
    for j in range(1, len(lang[i])):
        
        a,b=lang[i][j-1],lang[i][j]
        if not uf.same(a, b):
            uf.union(a, b)


if uf.len()==1:
    YES()
else:
    NO()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7


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)
        
        self.tree = [True] * (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 x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

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

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

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

    
    def is_tree(self, x):
        return self.tree[self.find(x)]

N,M=MAP()

lang=[[] for i in range(M+1)]
for i in range(N):
    for j in LIST()[1:]:
        lang[j].append(i+1)

uf=UnionFind(N)
for i in range(1, M+1):
    for j in range(1, len(lang[i])):
        a,b=lang[i][j-1],lang[i][j]
        if not uf.same(a, b):
            uf.union(a, b)

root=uf.find(1)
for i in range(2, N+1):
    if uf.find(i)!=root:
        NO()
        exit()
YES()

Solution (Python):
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def bfs(path, start, visited_set):
    que = deque([start])
    while 1:
        if len(que) == 0:
            break;
        nd = que.popleft()
        for adj in path[nd]:
            if adj not in visited_set:
                visited_set.add(adj)
                que.append(adj)



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    path = {}
    ofset = 1000000
    for i in range(N):
        path[i + ofset] = []

    for i in range(N):
        input_raw = read_func().strip().split()
        K = int(input_raw[0])
        for j in range(1, K + 1):
            path[i + ofset].append(int(input_raw[j]))
            if int(input_raw[j]) not in path:
                path[int(input_raw[j])] = [i + ofset]
            else:
                path[int(input_raw[j])].append(i + ofset)
    visited_set = set([])
    bfs(path, ofset, visited_set)
    for i in range(N):
        if i + ofset not in visited_set:
            print "NO"
            return
    print "YES"

if __name__ == '__main__':
    main()

Solution (Python):
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)
    a[x] = a[y] = min(x, y)


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')

Solution (Python):
input = __import__('sys').stdin.readline
MIS = lambda: map(int,input().split())

n, m = MIS()
adj = [[] for i in range(n+1)]
speaker = [[] for i in range(m+1)]
for i in range(n):
    lang = list(MIS())[1:]
    for x in lang: speaker[x].append(i+1)
for L in speaker:
    for i in range(len(L)-1):
        adj[L[i]].append(L[i+1])
        adj[L[i+1]].append(L[i])

vis = [False]*(n+1); vis[1] = True
stack = [1]
while stack:
    p = stack.pop()
    for q in adj[p]:
        if vis[q]: continue
        vis[q] = True; stack.append(q)
print("YES" if sum(vis) == n else "NO")

Solution (Python):
import sys
sys.setrecursionlimit(100000)

n,m=map(int,input().split())
f=lambda x:int(x)-1

langs=[[] for _ in range(m)]
speakers=[[] for _ in range(n)]
used_langs=[False]*m
used_speakers=[False]*n

for i in range(n):
  *l,=map(f,input().split()[1:])
  speakers[i].extend(l)
  for j in l:
    langs[j].append(i)

def dfs(n):
  if used_speakers[n]:
    return
  used_speakers[n]=True
  for i in speakers[n]:
    if used_langs[i]:continue
    used_langs[i]=True
    for j in langs[i]:
      dfs(j)

dfs(0)
if not False in used_speakers:
  print("YES")
else:
  print("NO")

Solution (Python):
n, m = map(int, raw_input().split())
g = [[] for i in xrange(m)]
for i in xrange(n):
    ipt = map(int, raw_input().split())
    k = ipt[0]
    for e in ipt[1:]:
        g[e-1].append(i)
parent = range(n)
def root(x):
    if x == parent[x]:
        return x
    parent[x] = root(parent[x])
    return parent[x]
def unite(x, y):
    px = root(x)
    py = root(y)
    if px < py:
        parent[py] = px
    elif px > py:
        parent[px] = py
    return min(px, py)
for e in g:
    for i in xrange(len(e)-1):
        unite(e[i], e[i+1])
for i in xrange(n):
    root(i)
print "YES"*(sum(parent) == 0) or "NO"

Solution (Python):
from collections import defaultdict
def main():
    N, M = [int(i) for i in input().split()]
    L = [[] for _ in range(M+1)]
    for i in range(N):
        for j in map(int, input().split()[1:]):
            L[j].append(i)
    uf = UnionFind()
    for i, l in enumerate(L):
        
        if not l:
            continue
        a = l[0]
        for b in l[1:]:
            
            uf.union(a, b)
    
    print("YES" if uf.size(0) == N else "NO")
    

class UnionFind(object):

    def __init__(self):
        self.table = defaultdict(lambda: -1)

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

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

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

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

if __name__ == "__main__":
    main()

Solution (Python):
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

(N, M) = reads()

d = defaultdict(list)
V = set()

for i in range(N):
  V.add(("p", i+1))
for j in range(M):
  V.add(("l", j+1))

for i in range(1, N+1):
  Ls = reads()[1:]
  for j in Ls:
    d[("l", j)].append(("p", i))
    d[("p", i)].append(("l", j))

def walk(v):
  V.discard(v)
  for w in d[v]:
    if w in V:
      walk(w)




v = ("p", 1)
walk(v)



print("NO" if len([v for v in V if v[0] == "p"]) > 0 else "YES")

Solution (Python):


import collections
import sys
sys.setrecursionlimit(100000)

def dfs(i):
    if visited[i] == 1:
        return
    visited[i] = 1
    for j in speakers[i]:
        if used_lang[j] == 1:
            continue
        used_lang[j] = 1
        for k in langs[j]:
            dfs(k)


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

langs = collections.defaultdict(list)
speakers = [[] for _ in range(N)]

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

visited = [0] * N
used_lang = [0] * M
dfs(0)

if 0 not in visited:
    print("YES")
else:
    print("NO")