/* 문제 */
지민은 파티에 가서 이야기하는 것을 좋아한다. 우리는 파티에 갈 때마다 지민이가 가장 좋아하는 이야기를 들려준다. 지민은 이야기를 할 때 사실대로 말하거나 지나치게 과장한다. 과장하는 것이 분명히 훨씬 더 재미있기 때문에 가능한 한 과장하려고 노력합니다. 하지만 지민은 거짓말쟁이로 알려지는 것을 싫어한다. 문제는 그 이야기의 진실을 아는 사람이 거의 없다는 것입니다. 따라서 이 사람들이 파티에 오면 지민은 사실대로 말할 수밖에 없다. 물론 한 쪽에서는 진실을, 다른 쪽에서는 과장을 들으면 지민은 거짓말쟁이로 알려질 것이다. 지민이는 이 모든 것을 피해야 한다.
인원수 N이 주어진다. 그리고 그 이야기의 진실을 아는 자가 주어진다. 그리고 각 파티에 오는 사람들의 수가 표시됩니다. 지민은 모든 파티에 있어야 해. 이때 지민이 거짓말쟁이로 알려지지 않고 과장된 이야기를 할 수 있는 최대 파티 수를 찾는 프로그램을 작성하세요.
작년에 그래픽도 모르고 풀려고 하다가 실패한 문제입니다.
dfs로 구현되었습니다.
# 정답 코드
import sys
sys.setrecursionlimit(10**9)
def dfs(graph, v, heard):
if heard(v) == 1: # 진실을 아는 사람일 경우
for i in graph(v):
if heard(i) == 0:
heard(i) = 1
dfs(graph, i, heard)
n, m = map(int, input().split())
t = list(map(int,input().split())) # 진실을 아는 사람들
del t(0)
# 아무 것도 못들은 사람: 0, 진실을 아는 사람: 1
heard = (0 for _ in range(n+1))
for i in t:
heard(i) = 1
# 같은 파티에 오는 사람들끼리 연결
graph = (() for _ in range(n+1))
parties = ()
for _ in range(m):
party = list(map(int, input().split()))
del party(0)
parties.append(party)
for a in party:
for b in party:
if a != b:
graph(a).append(b)
for i in t:
dfs(graph, i, heard) # 진실을 아는 사람들에 대해 dfs
res = 0
for party in parties:
possible = True
for p in party:
if heard(p) == 1:
possible = False
break
if possible:
res += 1
print(res)각 사람에게 번호가 부여됩니다. 들은 목록에서 듣지 못한 사람은 0으로, 진실을 아는 사람은 1로 표시되며, 같은 파티에 온 각 사람은 차트 목록에 저장됩니다. 그리고 진실을 알고 있는 각 사람을 출발점으로 하여 dfs를 실행하면 진실을 말해야 하는 모든 사람들도 1로 표시됩니다. 당원 중 한 사람이라도 진실을 안다면 당은 거짓말을 할 수 없다. 따라서 아무도 진실을 알지 못하는 당사자의 수가 주어진다(모든 참여자의 들은 값은 0이다).
