SCC 알고리즘 2가지

백준 2150: Strongly Connected Component

kosaraju's Algorithm 풀이
https://www.acmicpc.net/source/40831992

로그인

BFS와 Reverse DFS를 사용하여 BFS를 통해 스택에 담긴 노드들을 Reverse DFS를 사용하여 SCC를 찾아냅니다.

Tarjan Algorithm 풀이
https://www.acmicpc.net/source/41339158

로그인

한 번의 DFS를 통해 SCC의 번호를 매겨 찾아냄 SCC 노드끼리 DAG를 만들어내는데 용이합니다