강결합 컴포넌트

강한 연결 요소 (SCC) - 타잔 알고리즘

[백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간.. hyeo-noo.tistory.com 학교 알고리즘 수업 때 코사라주 알고리즘을 활용한 SCC풀이법을 배웠다. 하지만 구글링을 해보니 코사라주 알고리즘보다는 타잔 알고리즘이 구현이 어렵지만 활용도가 더 높다고 해서 공부해 보았다. 타잔 알고리즘 1번 정점에서 dfs를 시작해 2, 3, 4번 정점을 순서대로 방문했다고 하자. 타잔 알고리즘에서는 방문할 때마다 임의의 sta..