SCC. [2150]

[1. 문제 설명]

방향 그래프가 주어졌을 때,

그래프 내 SCC(=강결합 컴포넌트) 개수와 각 컴포넌트에 속한 정점 번호를 출력한다.

---

[2. 풀이 접근]

강결합 컴포넌트 (이하 SCC) 란 방향 그래프에서

서로 다른 임의의 두 정점 u ~> v 와 v ~> u 로 가는 경로가 존재하는 컴포넌트를 말한다.

위 그림에서 (a, b) (b, e) (e, a) 는 모두 경로가 존재하므로,

같은 SCC 에 속하게 된다.

 

이러한 SCC 를 구하는 알고리즘 중 타잔 알고리즘을 적용하여 문제를 해결하도록 한다.

타잔 알고리즘 동작 원리는 아래 링크를 참조하도록 한다.

---

[3. 코드]