import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
def DFS(now):
global id
stack.append(now)
visited[now] = nowid = id
for next in graph[now]:
if not visited[next]:
id += 1
DFS(next)
if visited[next] <= nowid:
indegree[next] -= 1
visited[now] = min(visited[now],visited[next])
if visited[now] == nowid:
scc.append([]); sccindegree.append(0)
while 1:
x = stack.pop()
scc[-1].append(x)
sccindegree[-1] += indegree[x]
visited[x] = 1e7
if x == now:
break
for _ in range(int(input())):
N,M = map(int,input().split())
graph = [[] for i in range(N)]; indegree = [0]*N
for _ in range(M):
a,b = map(int,input().split())
graph[a-1].append(b-1)
indegree[b-1] += 1
visited = [0]*N
stack,scc,sccindegree = [],[],[]
for i in range(N):
if not visited[i]:
id = 1
DFS(i)
print(sccindegree.count(0))
위상정렬 + SCC로 해결하였다.
처음에는 그냥 위상정렬 문제라고 생각했다. 위상정렬으로 indegree가 0인 도미노를 찾고, 전부 넘어뜨려 본 뒤(indegree가 0이면 다른 도미노에 의해 넘어질 수가 없으므로 무조건 넘어뜨려야한다) 만약 도미노가 남아있다면 나머지 도미노는 랜덤으로 넘어뜨리는 방식으로 풀었다.
그러나 이 방법은 틀렸습니다 가 떴다. 이유는 금방 생각해낼 수 있었다. indegree가 0인 도미노를 모두 넘어뜨리고 나면 SCC를 이루는 도미노만 남게 되는데, SCC간에도 먼저 넘어뜨려야하는 순서가 있기 때문이다.
따라서 "SCC의 indegree"를 구하는것이 이 문제의 핵심 포인트이다.
풀이를 설명하면,
1. 도미노의 관계에 따라서 도미노의 그래프와 indegree를 저장한다.
2. 타잔 알고리즘으로 SCC를 찾는다. SCC를 구하면서 각 SCC의 indegree도 구해준다.
(SCC의 indegree란, 같은 SCC 요소간의 indegree를 제외한 모든 요소의 indegree의 합을 의미한다)
3. indegree가 0인 SCC의 개수를 출력한다.
오늘의 교훈) SCC 알고리즘을 활용해서 다양한 문제를 해결하자