[백준][Python] 1043번 거짓말 - 그래프, DFS

 

 

Python

import sys
input = sys.stdin.readline

people, party = map(int, input().split())
graph = [set() for _ in range(people+1)]
true = input()
true = int(true) if len(true) == 1 else list(map(int, true.split()))

if true == 0:
    print(party)
    sys.exit(0)

parties = []
for _ in range(party):
    p = input()
    parties.append(int(true) if len(p) == 1 else list(map(int, p.split())))


for p in parties:
    for i in range(1, p[0]+1):
        for j in range(1, p[0]+1):
            if i != j:
                graph[p[i]].add(p[j])

visit = [0]*(people+1)
for t in true[1:]:
    stack = [t]  # dfs
    while stack:
        x = stack.pop()
        if visit[x] == 0:
            visit[x] = 1
            stack += list(graph[x])

ans = party
for p in parties:
    for i in range(1, len(p)):
        if visit[p[i]] == 1:
            ans -= 1
            break
print(ans)