https://www.acmicpc.net/problem/20504
20504번: I번은 쉬운 문제
2030년, Farmer John은 선린 인터넷 컴퍼니에서 소프트웨어 개발자이자 검색 팀장으로 근무하고 있다. John의 강한 의지에 따라 검색 팀에서는 모든 소프트웨어의 개발을 테스트 주도 개발(test-driven
www.acmicpc.net
각 함수마다 실행 과정에서 호출할 가능성이 있는 함수들의 목록이 주어질 때, 주어진 테스트 케이스 내 함수를 실행해 모든 함수가 호출할 가능성이 존재하도록 하는 테스트케이스의 최소 개수를 구하는 문제다.
최소의 테스트케이스만을 이용해 모든 함수가 호출되도록 하기 위해 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)