import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**4)
def DFS(now):
global id
nowid = visited[now] = id
stack.append(now)
for next in graph[now]:
if sccnum[next]:
continue
if not visited[next]:
id += 1
DFS(next)
visited[now] = min(visited[now],visited[next])
if visited[now]==nowid:
n = len(scc); scc.append([])
while 1:
x = stack.pop()
sccnum[x] = n; scc[-1].append(x)
if x==now:
break
while 1:
try:
N,M = map(int,input().split())
except:
break
data = [*map(int,input().split())]
graph = [[] for i in range(N+1)]
for i in range(M):
graph[data[i*2]].append(data[i*2+1])
scc,stack = [[]],[]; n = 0
sccnum,visited,outdegree = [[0]*(N+1) for i in range(3)]
for i in range(1,N+1):
if not visited[i]:
id = 1
DFS(i)
outdegree = [0]*(N+1)
for i in range(1,N+1):
for j in graph[i]:
if sccnum[i]!=sccnum[j]:
outdegree[sccnum[i]] += 1
result = []
for i in range(1,len(scc)):
if not outdegree[i]:
result += scc[i]
print(*sorted(result))
SCC 응용문제.
도미노 [백준 4196번] 도미노 (Python3) (tistory.com) 와 거의 유사한 문제이다. 도미노가 indegree가 0인 개수를 구하는 문제였다면, 이 문제는 outdegree가 0인 scc를 구하면 된다.
즉, 풀이를 요약하면,
1. 타잔알고리즘으로 SCC를 구한다.
2. 각 SCC의 outdegree를 구한다.
3. outdegree가 0인 SCC의 노드를 출력한다.
로 정리할 수 있다.
풀이 자체는 간단한 문제였는데, outdegree라는 용어가 있다는 것을 알게된 문제였다. 위상정렬 알고리즘에서 indegree는 배웠기 때문에 그냥 in 반대니까 outdegree라고 놓고 풀었는데, 실제로 있는 용어였다. (당연한가?)
오늘의 교훈) outdegree를 풀이에 활용하자