Directed Graph에서 SCC(Strongly Connected Component)를 추출한다. 아래 슈도코드에서는 각 정점이 속한 SCC 번호를 담은 배열을 구한다.(배열 vertex2scc[N]) Time complexity: worst: O(V + E) Pseudocode:

백준 1238 : 파티 유향 그래프의 노드와 변, 그리고 변의 비용이 주어질 때, 각 노드에서 정해진 목적지 노드까지 변을 타고 간 다음, 다시 원래대로 돌아오는 비용이 가장 큰 노드를 구하는 문제이다. 사실 이 문제는 다익스트라(O(N + E)) 두 번만으로 풀리는데, 한번 플로이드 와샬 알고리즘을 써보고 싶어서 그렇게 했다가 많이 느려졌다. (O(N^3)) 추후 다시 구현해볼 예정이다. […]