Directed Graph의 모든 정점이 다른 모든 정점에 도달 가능한 경우, "Strongly Connected" 라고 한다. Strongly Connected Components(SCC)는 가장 큰 strongly connected subgraph이다.

예를 들어, 다음의 경우 SCC는 세개이다.

Kosaraju's Algorithm

1. DFS를 해서 adjacency nodes를 모두 순회하면 현재 node를 Stack에 추가한다.
2. Transpose Graph를 새로 만든다.
3. Stack에서 vertex를 pop한다. 해당 v를 source로 하여 Transpose Graph를 DFS한다. 이때 방문하게 되는 vertices가 하나의 SCC이다.

이 방법으로 SCC를 O(V+E)의 시간 복잡도로 찾을 수 있다.

Tarjan's Algorithm

시간 복잡도는 O(V+E)이다.