import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
def DFS(now):
global num
nownum = num
visited[now] = num
stack.append(now)
for next in graph[now]:
if not visited[next]:
num += 1
DFS(next)
visited[now] = min(visited[now],visited[next])
if visited[now] == nownum:
scc.append([])
while 1:
x = stack.pop()
visited[x] = 1e6
scc[-1].append(x)
if x==now:
break
N,M = map(int,input().split())
graph = [[] for i in range(N+1)]
for i in range(M):
a,b = map(int,input().split())
graph[a].append(b)
visited = [0]*(N+1)
scc = []; stack = []
for i in range(1,N+1):
if not visited[i]:
num = 1
DFS(i)
scc = sorted([*map(sorted,scc)])
print(len(scc))
for s in scc:
print(*s,-1)
SCC 기본문제이다.
기본문제 플래티넘답게 구현이 꽤 까다로웠다. 코드를 베끼기보다는 원리노트를 보고 직접 구현하려고 시도했는데, 예상치 못한 반례들이 꽤 많았다.
원리는 https://yjg-lab.tistory.com/188 를 참조하였다.
내가 한 실수를 정리하면,
1. DFS에서 각 노드의 탐사번호를 노드의 깊이로 해선 안된다.
2. 한번의 DFS로 모두 탐사할 수 있는것이 아니다. 방문하지 않은 모든 노드에 대해서 DFS를 해주어야한다.
3. 2번에서 서로 다른 scc끼리 간섭될 수 있으므로 이미 scc에 넣은 노드는 따로 처리해주어야한다.
오늘의 교훈) SCC를 활용해서 다양한 문제를 해결해보자