[백준] 20504 - I번은 쉬운 문제 Python

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

20504번: I번은 쉬운 문제

각 함수마다 실행 과정에서 호출할 가능성이 있는 함수들의 목록이 주어질 때, 주어진 테스트 케이스 내 함수를 실행해 모든 함수가 호출할 가능성이 존재하도록 하는 테스트케이스의 최소 개수를 구하는 문제다.

 

최소의 테스트케이스만을 이용해 모든 함수가 호출되도록 하기 위해 scc 집합의 연결관계를 확인해 본다. 예를 들어, scc 집합 1이 scc 집합 2로 갈 수 있도록 연결되어 있다면 scc 집합 1에 속하는 함수를 하나 호출하면 scc 집합 1과 scc 집합 2 에 속하는 함수들이 모두 호출된다. 따라서, 반드시 호출되어야 하는 scc 집합들을 구한 후, 해당 집합들에 있는 요소를 테스트케이스들에서 적어도 하나 포함하고 있는지 확인한다. 

 

정리하자면, 다음 방법을 통해 풀이할 수 있다.

- scc 집합을 구한다.

- 다른 scc 집합에서 도달할 수 없는 (=in_degree 가 0 인) scc 집합들을 구한다.

- 테스트 케이스에서 이러한 집합들의 요소중 한 개를 포함하고 있는지 확인한다.

- 테스트케이스에서 집합의 요소들 중 적어도 한개를 포함하지 못한 in_degree 가 0 인 집합이 있다면 -1 을 출력한다.

 

코드로 나타내보면 다음과 같다.

from sys import stdin, setrecursionlimit
setrecursionlimit(10**6)


def dfs(node):
    global node_id, scc_id
    node_id += 1
    d[node] = node_id
    stack.append(node)
    parent = d[node]
    for n in graph[node]:
        if d[n] == 0:
            parent = min(parent, dfs(n))
        elif not finished[n]:
            parent = min(parent, d[n])
    if parent == d[node]:
        scc_id += 1
        while 1:
            n = stack.pop()
            finished[n] = 1
            scc_d[n] = scc_id
            if n == node:
                break
    return parent


N, M = map(int, stdin.readline().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    u, v = map(int, stdin.readline().split())
    graph[u].append(v)


stack = []
d = [0]*(N+1)
scc_d = [0]*(N+1)
finished = [0]*(N+1)
node_id = 0
scc_id = 0
cnt = 0
ans = 0

for node in range(1, N+1):
    if d[node] == 0:
        dfs(node)

in_degree = [0]*(scc_id+1)
for node in range(1, N+1):
    for n in graph[node]:
        if scc_d[n] != scc_d[node]:
            in_degree[scc_d[n]] += 1

for i in range(1, scc_id+1):
    if in_degree[i] == 0:
        cnt += 1

T = int(stdin.readline())

for _ in range(T):
    node = int(stdin.readline())
    if in_degree[scc_d[node]] == 0:
        in_degree[scc_d[node]] = 1
        ans += 1
        cnt -= 1

print(ans if cnt == 0 else -1)