Submission #7564002

---

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 = 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 Info

Judge Result