[6기 강남 조유석] Strongly Connected Component

안녕하세요. 강남멤버십 23-1기 조유석입니다.

이번 포스팅에서는 Strongly Connected Component 에 대해 알아보겠습니다.

Strongly Connected Component

Directed Graph의 정점의 부분집합 S가 「임의의 두 정점 u, v를 가지는 경우 u에서 v에 도달할 수 있다」라는 조건에 만족하고 있을 때 S는 강한 연결이라고 말할 수 있습니다. 정점의 강한 연결인 집합 S에 다른 어떤 정점 집합을 더해도 강한 연결이 될 수 없을 때 S를 Strongly Connected Component(강한 연결 성분)이라고 말합니다. 어떠한 Directed Graph도 몇 개의 Strongly Connected Componet의 공통부분을 가지지 않는 합집합으로 분해할 수 있습니다. 이것을 강한 연결 성분 분해라고 부릅니다. Strongly Connected Component 를 1개의 정점으로 변형하는 것으로 DAG(Directed Acyclic Graph, 닫힌 경로를 가지지 않는 Directed Graph)가 됩니다.

강한 연결 성분 분해

강한 연결 성분 분해는 2회의 간단한 DFS에 의해 분해할 수 있습니다. 1번째 DFS에서는 적당한 정점에서 시작해, 아직 통과하지 않은 정점을 찾으면서 post order로 번호를 붙입니다. 아직 통과하지 않은 정점이 있는 경우에는 다시 그곳에서 부터 시작하는 것을 반복합니다.

2번째 DFS에서는 그래프의 모든 변을 역방향으로 해서, 번호가 제일 큰 곳에서 부터 DFS를 시작합니다. 통과할 수 있었던 정점의 집합이 1개의 Strongly Connected Component(강한 연결 성분)이 됩니다. 그 후 통과하지 않는 정점이 있는 경우는, 그 중에 번호가 제일 큰 곳에서 다시 DFS를 반복합니다.

Strongly Connected Component를 1개의 정점으로 변형하면 DAG가 된다 라는 것은 앞에서 설명했습니다. 이 때 번호가 제일 큰 정점이라는 것은 DAG의 선두에 Strongly Connected Component에 속한다는 것을 알 수 있습니다. 변을 역방향으로 하면, 이 선두의 Strongly Connected Component로부터 밖으로 나갈 수 없습니다. Strongly Connected Component 중에서는 변을 역방향으로 해도 도달하는 것이 가능한 정점의 집합은 변하지 않으므로, 2번째의 DFS에서 Strongly Connected Component의 모든 정점에 도달할 수 있다는 것을 알 수 있습니다.

이 알고리즘은 DFS를 2번 한 것뿐이므로 계산량이 O(|V|+|E|)가 됩니다.

이상으로 Strongly Connected Component에 대해 알아보았습니다.

감사합니다.

Reference

  - ‘프로그래밍 콘테스트 챌린징’ - Takuya Akiba, Yoichi Iwata, Masatoshi Kitagawa 저