문제

https://www.acmicpc.net/problem/1043

Input1)
4 3
0
2 1 2
1 3
3 2 3 4
Output1)
3
Input2)
4 1
1 1
4 1 2 3 4
Output2)
0
Input3)
4 1
0
4 1 2 3 4
Output3)
1

point

그래프로 풀이

• '진실을 아는 자'(A)와 같은 파티에 있는 사람들은 '진실을 아는 자'(B)가 된다.
  : 이것은 재귀적으로 '알게 된 자'(B)와 같은 파티에 있는 사람들도 '진실을 아는 자'(C)가 된다.
• 같은 파티에 있는 사람들 끼리 연결된 간선이 있다고 생각
• 초기 '진실을 아는 자' 노드에서 그래프 탐색을 하여 도달 할 수 있는 사람(노드)는 진실을 알게된다.
  : 같은 그래프에 속하는 노드
• 즉, 초기 '진실을 아는 자' 노드에서 도달 할 수 없는 노드(사람)로만 구성된 파티에서 거짓말을 할 수 있다.

그래프 구성

• 같은 파티에 속한 사람들을 간선으로 이어준다.
• 같은 파티 내에 사람들끼리 경로가 존재하기만 하면 되므로, 모든 간선을 이을 필요 없다.

pp = [[] for _ in range(m)] #party people
for i in range(m):
    pp[i] = [int(x) for x in input()[2:].split()]
    last = pp[i][0]
    for p in pp[i][1:]:
        graph[last].add(p)
        graph[p].add(last)
        last = p

탐색

• 탐색은 DFS로 구현했다.
• 그래프 탐색의 시작점은 know_truth의 멤버 (초기부터 '진실을 아는 자')
• can_lie
  : 거짓말 해도 되는 대상 사람이다.
  : 아직 그래프 탐색을 통해 도달된 적 없는 노드다.
• 탐색 후 방문 노드 i : vis[i] == 1 를 can_lie에서 삭제한다.

모든 know_truth로부터 탐색 X

• know_truth 중 이미 다른 know_truth로부터의 탐색 중 도달 된 적 있는 노드일 경우는 (같은 그래프내에 있는 경우) 다시 그 그래프를 탐색 할 필요가 없다.

else:
    asw = [0] * (n + 1)
    can_lie = set(list(range(1,n+1)))
    for a in know_truth:
        if a in can_lie:
          vis = [0] * (n + 1)
          dfs(a)
          asw = [asw[i] + vis[i] for i in range(n + 1)]
          for i in range(1,n+1):
            if asw[i] > 0:
              can_lie.discard(i)

전체코드

n, m = [int(x) for x in input().split()]
know_truth = set()

s = input()
if s[0] != '0':
    for a in s.split()[1:]:
        know_truth.add(int(a))

graph = [set() for _ in range(n + 1)]

pp = [[] for _ in range(m)] #party people
for i in range(m):
    pp[i] = [int(x) for x in input()[2:].split()]
    last = pp[i][0]
    for p in pp[i][1:]:
        graph[last].add(p)
        graph[p].add(last)
        last = p

def dfs(s):
    global graph, vis
    vis[s] = 1
    for a in graph[s]:
        if vis[a] == 0:
            dfs(a)

if len(know_truth) == 0: #'know_truth'가 없는 경우 - 모든 파티에서 거짓말 가능
    print(m)
else:
    asw = [0] * (n + 1)
    can_lie = set(list(range(1,n+1)))
    for a in know_truth:
        if a in can_lie:
          vis = [0] * (n + 1)
          dfs(a)
          asw = [asw[i] + vis[i] for i in range(n + 1)]
          for i in range(1,n+1):
            if asw[i] > 0:
              can_lie.discard(i)
    
    count = 0
    for i in range(m):
        this_p = set(pp[i])
        if this_p-can_lie == set():
          count += 1
    print(count)