Submission #6436877

---

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 dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

d = dist_bfs(N+M,E,0)
ans = d[:N].count(-1)==0
print("YES" if ans else "NO")

Submission Info

Judge Result