SCC

SCC(Strongly Connected Component)는 강한 연결 요소이라고도 불리며

유향그래프 상에서 두 정점 u와 v에 대해 양방향으로 가는 경로가 모두 있을 때 같은 SCC에 있다고 표현합니다.

그래프를 SCC로 분리하는 방법으로는 타잔의 알고리즘을 사용합니다.

이 알고리즘은 정점을 담는 하나의 스택과 한 번의 DFS만을 이용하여 분리하는데

원리는 앞서 배운 간선 분류를 이용하여 아래와 같이 설명할 수 있습니다.

u의 자손 v에 대하여 v를 루트로 하는 서브트리에서 v보다 먼저 발견된 정점으로 가는 역방향 간선이 있을 때,

v보다 먼저 발견되었으면서 아직 SCC로 묶여있지 않은 정점으로 가는 교차 간선이 있다면 간선 (u, v)를 끊어서는 안된다.

이는 절단점 확인 알고리즘과 일정 부분 유사하며 추가적으로 간선 (u, v)를 끊어야 한다고 판단이 될 경우

서브트리에 남아있는 정점들을 모두 한 SCC로 묶기 위해 스택을 사용합니다.

같은 SCC에 속하는 정점을 하나로 묶어 그래프를 압축하게 된다면

이 그래프는 DAG(Directed Acylic Graph)이 된다는 것을 이용하여 앞서 배운 위상정렬을 적용할 수 있으며

함수가 종료하기 직전에 SCC를 생성하기에 SCC는 위상정렬 역순으로 번호가 매겨져 좀 더 간편하게 구할 수 있습니다.

이러한 그래프를 SCC로 분리하는 타잔의 알고리즘은 한 번의 DFS를 사용하므로

시간복잡도는 정점 개수가 V 간선 개수가 E일 때 O(V + E)가 되는 것을 알 수 있습니다.

기본 문제

2150번: Strongly Connected Component

4196번: 도미노

4013번: ATM