130. Strongly Connected Component

유향 그래프에 존재하는 어떤 컴포넌트는 다음과 같은 조건을 만족할 경우 강결합 컴포넌트(Strongly Connected Component, SCC)라고 부른다.

• 컴포넌트에 속하는 임의의 두 정점 $u$와 $v$에 대해 $u$에서 $v$로 가는 경로와 $v$에서 $u$로 가는 경로가 모두 존재한다.
• 컴포넌트에 속하는 임의의 정점 $u$와 컴포넌트에 속하지 않는 임의의 정점 $v$에 대해 $u$에서 $v$로 가는 경로가 존재하지 않거나, $v$에서 $u$로 가는 경로가 존재하지 않는다.

그래프를 강결합 컴포넌트끼리 분리하면 같은 컴포넌트에 속한 정점들 사이에는 모두 경로가 존재하고, 다른 컴포넌트에 속한 정점들 사이에는 그렇지 않다. 따라서 같은 강결합 컴포넌트에 속한 정점들끼리 묶어서 새로운 그래프를 만들면 그 그래프는 DAG가 된다.

이런 그래프가 있을 때, 정점들을 강결합 컴포넌트끼리 분류하면 다음과 같다.

같은 색으로 칠해진 정점들 사이에는 전부 경로가 존재한다. 또한 그 정점들을 하나로 묶으면 그래프는 다음과 같이 더 간단한 형태의 DAG로 나타내어진다. 이렇게 그래프의 SCC를 묶어서 DAG를 만드는 것을 그래프 압축(Graph Condensation)이라고 한다.

---

그래프의 SCC를 구하는 알고리즘은 크게 두 가지가 알려져 있고, 이 블로그에서는 그것들을 차례로 살펴본다.

 

→ solved.ac tag: scc