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: Wrong Answer

Solution code:
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 (w for w in d[v] if w in V):
    walk(w)

# for (k, v) in d.items():
#   print(k, v)

v = V.pop()
walk(v)

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals

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

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

g = [1]
lg = set(L[0])
update = True
used = [False] * N
used[0] = True
while update:
    update = False
    for i in range(1, N):
        if used[i]:
            continue
        for l in lg:
            if l in L[i]:
                used[i] = True
                lg  = lg.union(set(L[i]))
# print(len(lg))
# print(lg)
if all(used):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, raw_input().split())
g = [[] for i in xrange(m)]
L = [None]*n
for i in xrange(n):
    ipt = map(int, raw_input().split())
    k = ipt[0]
    L[i] = ipt[1:]
    for e in L[i]:
        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
    else:
        parent[px] = py
    return min(px, py)
for e in g:
    for p in e:
        for q in e:
            unite(p, q)
print "YES"*(sum(parent) == 0) or "NO"

Submission status: Wrong Answer

Solution code:
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 = V.pop()
walk(v)

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

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
#CODE FESTIVAL 2016 Final-C
"""
グラフが連結であるかどうかを判定せよ？
距離が2以下になっているか判定せよかと思ったが、つながってればいいっぽい？
dfsで全部回れば良い
"""
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m = map(int,readline().split())
g = [[] for i in range(m)] #その言語を誰が使えるか
h = [] #誰がどの言語を使えるか
for i in range(n):
    lst1 = list(map(int,readline().split()))
    lst1 = lst1[1:]
    for j in lst1:
        g[j-1].append(i)
    h.append(lst1)


check = [0]*n
root = 0
check[root] = 1
deq = deque([root])
while deq:
    fr = deq.pop()
    for i in h[fr]:
        for j in g[i-1]:
            if check[j]:
                continue
            deq.append(j)
            check[j] = 1


if all(i==1 for i in check):
    print("YES")
else:
    print("NO")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
tree = [[] for _i in range(m+1)]
k = []
for i in range(n):
    x = list(map(int, input().split()))
    for j in x[1:]:
        tree[j].append(i)
    k.append(x[1:])

visit = [0 for _ in range(n)]
from collections import deque
q = deque([0])
while q:
    p = q.pop()
    if visit[p]==1:
        continue
    visit[p] = 1
    for i in k[p]:
        for j in tree[i]:
            if visit[j]==0:
                q.appendleft(j)
if sum(visit)==n:
    print("YES")
else:
    print("NO")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

n,m=map(int,input().split())
l=[]
for i in range(n):
    for j in input().split()[1:]:
        l.append((i,int(j)+n-1,1))
edge=np.array(l,dtype=np.int64).T
graph=csr_matrix(((edge[2],edge[:2])),(n+m,n+m))
ans=dijkstra(graph,directed=False,indices=0)
for i in ans[:n]:
    if i==float("inf"):
        print("NO")
        exit()
print("YES")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=[[]for i in range(m+1)]
par=[-1 for i in range(n)]
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(n):
    ll=[int(j) for j in input().split()[1:]]
    for j in ll:
        for k in l[j]:
            if root(i)!=root(k):
                connect(i,k)
        l[j].append(i)

for i in par:
    if -i==n:
        print("YES")
        exit()
print("NO")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
L = {}
for i in range(N):
    A = list(map(int, input().split()))
    for j, a in enumerate(A):
        if j == 0:
            continue
        if not a-1 in L.keys():
            L[a-1] = [i]
        else:
            L[a-1].append(i)

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        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
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

union = UnionFind(N)

for list_l in L.values():
    for l in list_l:
        union.Unite(l, list_l[0])

ans = "YES"
for i in range(N):
    if not union.isSameGroup(0, i):
        ans = "NO"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
people = [None] * N
from collections import defaultdict
lang = defaultdict(set)

for i in range(N):
  people[i] = list(map(int,input().split()))[1:]
  for l in people[i]:
    lang[l].add(i)
    
# 0番の人からたどって全員に行けるか
stack = [0]
seen = [False for i in range(N)]

while stack:
  p = stack.pop()
  if seen[p]:
    continue
  seen[p] = True
  la = people[p] # その人が話せる言語リスト
  for l in la:
    lang[l].remove(p)
    for pe in lang[l]:
      stack.append(pe)
  
for s in seen:
  if not s:
    print("NO")
    break
else:
  print("YES")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
D=[set() for i in range(M)]#i番目の言語を話せる人
L=[set() for i in range(N)]#i番目の人が話せる言語
for i in range(N):
    Li=list(map(int,input().split()))[1:]
    for l in Li:
        L[i].add(l-1)
        D[l-1].add(i)
seen=[False for i in range(N)]
seen[0]=True
def dfs(i):
    for l in L[i]:
        for k in D[l]:
            if not seen[k]:
                seen[k]=True
                dfs(k)

dfs(0)

if all(seen):
    print('YES')
else:
    print('NO')

Submission status: Time Limit Exceeded

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

# ユニオンファインド
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m= map(int, input().split())
a= [list(map(int, input().split())) for i in range(n)]
uf=UnionFind(m)
x=[0]*m
for i in range(n):
    if a[i][0]==1:
        x[a[i][1]-1]+=1
    else:
        for j in range(1,len(a[i])-1):
            uf.union(a[i][j]-1,a[i][j+1]-1)

y=uf.group_count()
if y==1:
    print('YES')
    exit()
else:
    count=0
    z=list(uf.all_group_members().values())

    for i in range(y):
        if len(z[i])>=2:
            count+=1
            if count>=2:
                print('NO')
                exit()
        else:
            if x[z[i][0]] == n:
                print('YES')
                exit()

            elif x[z[i][0]]>0:
                print('NO')
                exit()
    print('YES')

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from itertools import combinations

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

    def find(self, x):
        '''
        x が属するグループを探索
        '''
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        '''
        x と y のグループを結合
        '''
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

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

    def get_size(self, x):
        '''
        x が属するグループの要素数
        '''
        x = self.find(x)
        return self.size[x]

N,M = LI()
d = defaultdict(list)
for i in range(N):
    kl = LI()
    for l in kl[1:]:
        d[l].append(i)

uf = UF(N)
for k in d.keys():
    comb = combinations(d[k],2)
    for c in comb:
        uf.union(c[0],c[1])

if uf.get_size(0) == N:
    print('YES')
else:
    print('NO')

Submission status: Time Limit Exceeded

Solution code:


#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root

def main():
    N,M = MI()

    """
    全員が誰かと言語で話せて、それが連結ならOK
    """
    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes

    edge = [[] for _ in range(N)]
    language = [[] for _ in range(M)]
    for i in range(N):
        _,*L = MI_()
        for l in L:
            for b in language[l]:
                unite(i,b)
            language[l].append(i)
    print("YNEOS"[nodes[get_root(0)]!=-N::2])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

parent=[i for i in range(M)]
depth=[0 for i in range(M)]

def root(x):
  temp=x
  while x!=parent[x]:
    t=x
    x=parent[x]
    parent[t]=x
  parent[temp]=x
  return parent[x]
  
def same(x,y):
  return root(x)==root(y)

def union(x,y):
  x=root(x)
  y=root(y)
  if x==y:
    return
  if depth[x]>depth[y]:
    parent[y]=x
  else:
    parent[x]=y
    if depth[x]==depth[y]:
      depth[x]+=1
      
h=[None]*N
langs=set()
for i in range(N):
  k,*h=map(int,input().split())
  for j in range(k-1):
    langs.add(h[j]-1)
    union(h[j]-1,h[j+1]-1)
  langs.add(h[k-1]-1)
  
roots=set()
for l in langs:
  roots.add(root(l))
  
print(("NO","YES")[len(roots)==1])

Submission status: Time Limit Exceeded

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

parent=[i for i in range(M)]
depth=[0 for i in range(M)]

def root(x):
  temp=x
  while x!=parent[x]:
    x=parent[x]
  parent[temp]=x
  return parent[x]
  
def same(x,y):
  return root(x)==root(y)

def union(x,y):
  x=root(x)
  y=root(y)
  if x==y:
    return
  if depth[x]>depth[y]:
    parent[y]=x
  else:
    parent[x]=y
    if depth[x]==depth[y]:
      depth[x]+=1
      
h=[None]*N
langs=set()
for i in range(N):
  k,*h=map(int,input().split())
  for j in range(k-1):
    langs.add(h[j]-1)
    union(h[j]-1,h[j+1]-1)
  langs.add(h[k-1]-1)
  
roots=set()
for l in langs:
  roots.add(root(l))
  
print(("NO","YES")[len(roots)==1])

Submission status: Time Limit Exceeded

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

parent=[i for i in range(M)]
depth=[0 for i in range(M)]

def root(x):
  while x!=parent[x]:
    x=parent[x]
  return parent[x]
  
def same(x,y):
  return root(x)==root(y)

def union(x,y):
  x=root(x)
  y=root(y)
  if x==y:
    return
  if depth[x]>depth[y]:
    parent[y]=x
  else:
    parent[x]=y
    if depth[x]==depth[y]:
      depth[x]+=1
      
h=[None]*N
langs=set()
for i in range(N):
  k,*h=map(int,input().split())
  for j in range(k-1):
    langs.add(h[j]-1)
    union(h[j]-1,h[j+1]-1)
  langs.add(h[k-1]-1)
  
roots=set()
for l in langs:
  roots.add(root(l))
  
print(("NO","YES")[len(roots)==1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("YES")  # type: str


def no():
    print("NO")  # type: str


class UnionFind(object):

    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def main():

    N, M = map(int, input().split())
    L = [0]*N
    for i in range(N):
        K, *L[i] = list(map(int, input().split()))
    # 前Nは人、後ろMは言語
    uf = UnionFind(N+M)

    for i in range(N):
        for l in L[i]:
            # 人iは言語L[i]と同じグループ
            uf.unite(i, N+l-1)

    # print(uf.tree)
    # 人はすべて同じグループであるか
    flag = True
    for i in range(N):
        if not uf.same(0, i):
            flag = False
            break
    if flag:
        yes()
    else:
        no()

    pass


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix


def main():
    n, m = map(int, sys.stdin.readline().split())
    can_speak = [[] for _ in range(m + 1)]
    for i in range(n):
        *languages, = map(int, sys.stdin.readline().split())
        for l in languages[1:]:
            can_speak[l].append(i)
    
    G = [[0] * n for _ in range(n)]

    for language in can_speak:
        for j in range(len(language) - 1):
            G[language[j]][language[j+1]] = 1
            G[language[j+1]][language[j]] = 1

    shortest_path = dijkstra(csgraph=csr_matrix(G), directed=False, indices=0)

    if np.any(shortest_path == np.inf):
        ans = 'NO'
    else:
        ans = 'YES'
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
KL = [[int(i) for i in input().split()] for _ in range(N)]

lang = [[] for _ in range(M)]
for i in range(N) :
    for j in KL[i][1:] :
        lang[j-1].append(i)
        
visited = [False] * N
visited[0] = True
q = [0]
while q :
    cur = q.pop()
    for l in KL[cur][1:] :
        for m in lang[l-1] :
            if not visited[m] :
                q.append(m)
                visited[m] = True
                
if sum(visited) == N :
    print('YES')
else :
    print('NO')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, L):
    l2p = defaultdict(set)
    p2l = defaultdict(set)
    for i, l in enumerate(L):
        p2l[i+1] = set(l)
        for j in l:
            l2p[j].add(i+1)
    
    
    q = [1]
    done = set(q)
    while q:
        p = q.pop()
        for l in p2l[p]:
            for p2 in l2p[l]:
                if p2 not in done:
                    done.add(p2)
                    q.append(p2)
    return 'YES' if set(range(1, N+1)) == done else 'NO'



def main():
    N, M = read_int_n()
    L = [read_int_n()[1:] for _ in range(N)]
    print(slv(N, M, L))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

dicL = {}
for i in range(N):
  for l in L[i]:
    if l not in dicL:
      dicL[l] = [i]
    else:
      dicL[l].append(i)
#print(dicL)
E = [[] for _ in range(N)]
for k,v in dicL.items():
  if len(v) > 1:
    for i in range(len(v)-1):
      for j in range(i+1,len(v)):
        E[v[i]].append(v[j])
        E[v[j]].append(v[i])
#for i in range(N):
#  E[i] = set(E[i])
#print(E)
Visited = [0 for _ in range(N)]
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 else 'NO')

Submission status: Time Limit Exceeded

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

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

dicL = {}
for i in range(N):
  for l in L[i]:
    if l not in dicL:
      dicL[l] = [i]
    else:
      dicL[l].append(i)
#print(dicL)
E = [[] for _ in range(N)]
for k,v in dicL.items():
  if len(v) > 1:
    for i in range(len(v)-1):
      for j in range(i+1,len(v)):
        E[v[i]].append(v[j])
        E[v[j]].append(v[i])
for i in range(N):
  E[i] = set(E[i])
#print(E)
Visited = [0 for _ in range(N)]
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 else 'NO')

Submission status: Time Limit Exceeded

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:])

dicL = {}
for i in range(N):
  for l in L[i]:
    if l not in dicL:
      dicL[l] = [i]
    else:
      dicL[l].append(i)
#print(dicL)
E = [set() for _ in range(N)]
for k,v in dicL.items():
  if len(v) > 1:
    for i in range(len(v)-1):
      for j in range(i+1,len(v)):
        E[v[i]].add(v[j])
        E[v[j]].add(v[i])
#print(E)
Visited = [0 for _ in range(N)]
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 else 'NO')

Submission status: Time Limit Exceeded

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:])

dicL = {}
for i in range(N):
  for l in L[i]:
    if l not in dicL:
      dicL[l] = [i]
    else:
      dicL[l].append(i)
#print(dicL)
E = [set() for _ in range(N)]
for k,v in dicL.items():
  if len(v) > 1:
    for i in range(len(v)-1):
      for j in range(i+1,len(v)):
        E[v[i]].add(v[j])
        E[v[j]].add(v[i])
#print(E)
Visited = [0 for _ in range(N)]
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 else 'NO')

Submission status: Time Limit Exceeded

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:
    for p in stack_p:
        #p = stack_p.pop() # 調べる人を取り出す
        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の持つ言語をだれが話せるか調べる
        new_stack_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



print("NO")

Submission status: Time Limit Exceeded

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 = deque([1])
checked_p[1] = True
while stack_p:
    p = stack_p.pop() # 調べる人を取り出す
    #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
    #print(p, "lll", stack_lang)
    # 人pの持つ言語をだれが話せるか調べる
    new_stack_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
    #print("--", checked_p, checked_lang)
    #print("^^^", new_stack_p)
    if all(checked_p[1:]):
        print("YES")
        """
        print(checked_p)
        print(checked_lang)
        print(es_p)
        """
        exit()
    for i in new_stack_p:
        stack_p.append(i)

print("NO")
"""
print(checked_p)
print(checked_lang)
print(es_p)
"""

Submission status: Time Limit Exceeded

Solution code:
class Graph():
    def __init__(self,V):
        self.V = V
        self.verts = list(range(V))
        self.edges = [[] for _ in range(V)]
        self.E = 0

    def addEdge(self,f,t):
        self.edges[f].append(t)
        self.E += 1

    def deletebfs(self):
        queue = []
        queue.append(0)
        while queue != []:
            f = queue[0]
            queue.pop(0)
            for i in range(len(self.edges[f])):
                t = self.edges[f][-1]
                queue.append(t)
                self.edges[f].pop(-1)
                self.edges[t].pop(self.edges[t].index(f))
                self.E -= 2


if __name__ == '__main__':

    n,m = map(int, input().split(" "))
    k = [None for _ in range(n)]
    l = [[] for _ in range(n)]
    edge_num = 0
    for i in range(n):
        p = list(map(int, input().split(" ")))
        k[i] = p[0]
        l[i] = p[1:]
        edge_num += k[i]

    g = Graph(n+m)
    for i in range(n):
        for j in range(len(l[i])):
            person = i
            lang = l[i][j]+n-1
            g.addEdge(person,lang)
            g.addEdge(lang,person)
    g.deletebfs()
    if g.E == 0:
        print('YES')
    else:
        print('NO')