Submission #7564192

---

Source Code Expand

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:
    new_stack_p = [] # この次のループで調べる人の集合
    for p in stack_p:
        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の持つ言語をだれが話せるか調べる
        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
    else:
        break



print("NO")

Submission Info

Judge Result