Submission #6436418

---

Source Code Expand

#二部グラフで連結判定
N,M = map(int,input().split())
KL = [list(map(int,input().split())) for _ in [0]*N]

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

def connect_bfs(N,E,start):
    connect = {start}
    q = [start]
    while q:
        i = q.pop()
        for j in E[i]:
            if j in connect:continue
            connect.add(j)
            q.append(j)
    return connect

c = connect_bfs(N+M,E,0)
ans = len(c & set(range(N)))==N
print("YES" if ans else "NO")

Submission Info

Judge Result