강한 연결 요소 - 알고리즘카

앞에서 우리는 비순환 그래프를 위상 정렬하는 방법을 배웠습니다. 그러나 순환 그래프에서도 때때로 어떤 구조를 찾아야 할 때가 있으며, 이를 위해 강한 연결성이라는 개념을 도입해야 합니다.

정의. 방향 그래프의 두 정점이 서로 한쪽에서 다른 쪽으로 가는 경로와 그 반대 방향의 경로가 모두 존재하면, 두 정점은 강하게 연결되어 있다(영어: strongly connected)고 합니다. 다시 말해, 두 정점은 모두 어떤 사이클 위에 놓여 있습니다.

이러한 관계가 추이적이라는 것은 분명합니다. $a$와 $b$가 강하게 연결되어 있고 $b$와 $c$가 강하게 연결되어 있다면, $a$와 $c$도 강하게 연결되어 있습니다. 따라서 모든 정점은 강한 연결 요소로 나뉩니다. 이는 하나의 요소 안에서는 모든 정점이 강하게 연결되어 있고, 서로 다른 강한 연결 요소에 속한 정점 사이에는 강한 연결이 없도록 정점을 분할한 것입니다.

강한 연결 요소의 가장 간단한 예는 사이클입니다. 그러나 완전 그래프일 수도 있고, 여러 사이클이 복잡하게 얽힌 형태일 수도 있습니다.

개별 정점이 아니라 강한 연결 요소 자체로 구성된 그래프를 고려하는 경우가 많습니다. 이러한 그래프는 당연히 비순환 그래프가 되며, 다루기도 더 쉽습니다. 각 강한 연결 요소를 하나의 정점으로 압축하는 문제를 그래프의 응축이라고 부르며, 이제 그 해법을 설명하겠습니다.

#그래프의 응축

각 강한 연결 요소에 어떤 정점들이 속하는지 이미 알고 있다면, 응축 그래프를 만드는 것은 어렵지 않습니다. 인접 리스트를 약간 조작하면 되는데, 모든 간선에 대해 정점 번호를 해당 정점이 속한 요소의 번호로 바꾼 다음, 각 요소에 속한 모든 정점의 인접 리스트를 합치면 됩니다. 따라서 원래 문제를 곧바로 요소 자체를 찾는 문제로 환원하겠습니다.

보조정리. dfs를 실행합시다. $A$와 $B$가 서로 다른 두 강한 연결 요소이고, 축약 그래프에서 이들 사이에 간선 $A \to B$가 있다고 합시다. 그러면 다음이 성립합니다.

$$ \max\limits_{a \in A}(tout_a) > \max\limits_{b\in B}(tout_b) $$

증명. dfs가 두 컴포넌트 중 어느 쪽에 먼저 들어가는지에 따라 두 가지 경우로 나누어 살펴봅시다.

컴포넌트 $A$에 먼저 도달했다고 합시다. 즉, 어느 시점에 dfs가 컴포넌트 $A$의 어떤 정점 $v$에 들어가며, 이때 컴포넌트 $A$와 $B$의 나머지 정점은 모두 아직 방문하지 않은 상태입니다. 그런데 조건에 따라 응축 그래프에 간선 $A \to B$가 있으므로, 정점 $v$에서는 컴포넌트 $A$ 전체뿐만 아니라 컴포넌트 $B$ 전체에도 도달할 수 있습니다. 이는 정점 $v$에서 시작한 깊이 우선 탐색이 컴포넌트 $A$와 $B$의 모든 정점을 지나간다는 뜻이며, 따라서 이 정점들은 탐색 트리에서 $v$의 자손이 되고, 임의의 정점 $u \in A \cup B, u \ne v$에 대해 $tout_v] > tout_u$가 성립합니다. 이것이 바로 주장한 내용입니다.

두 번째 경우는 더 간단합니다. 조건에 따라 $B$에서 $A$로는 도달할 수 없으므로, $B$에 먼저 도달했다면 dfs는 $A$에 들어가기도 전에 $B$의 모든 정점에서 빠져나옵니다.

이 사실로부터 해법의 첫 번째 부분이 도출됩니다. 정점들을 탈출 시각의 내림차순으로 정렬합시다(말하자면 위상 정렬을 하는 것이지만, 사이클이 있는 그래프에서 하는 것입니다). 정렬에서 첫 번째 정점의 강한 연결 요소를 살펴봅시다. 이 요소로는 다른 요소에서 들어오는 간선이 확실히 하나도 없습니다. 그렇지 않다면 첫 번째 정점의 $tout$이 최대이므로 보조정리의 조건이 깨지게 됩니다. 따라서 그래프의 모든 간선을 뒤집으면, 이 정점에서는 자신의 강한 연결 요소 $C^\prime$에만 도달할 수 있고 그 밖의 어디에도 도달할 수 없습니다. 원래 그래프에 다른 요소로부터 오는 간선이 없었다면, 전치 그래프에는 다른 요소로 가는 간선이 없을 것이기 때문입니다.

첫 번째 정점에 대해 이 작업을 마친 후에는 위상 정렬된 목록을 따라 계속 진행하면서, 아직 연결 요소를 표시하지 않은 정점들에 대해 같은 작업을 반복할 수 있습니다.

vector<int> g[maxn], t[maxn];
vector<int> order;
bool used[maxn];
int component[maxn];
int cnt_components = 0;

// топологическая сортировка
void dfs1(int v) {
    used[v] = true;
    for (int u : g[v]) {
        if (!used[u]) 
            dfs1(u);
    order.push_back(v);
}

// маркировка компонент сильной связности
void dfs2(int v) {
    component[v] = cnt_components;
    for (int u : t[v])
        if (component[u] == 0)
            dfs2(u);
}


// в содержательной части main:

// транспонируем граф
for (int v = 0; v < n; v++)
    for (int u : g[v])
        t[u].push_back(v);

// запускаем топологическую сортировку
for (int i = 0; i < n; i++)
    if (!used[i])
        dfs1(i);

// выделяем компоненты
reverse(order.begin(), order.end());
for (int v : order)
    if (component[v] == 0)
        dfs2(v), cnt_components++;

TL;DR:

정점들을 탈출 시각의 내림차순으로 정렬합니다.
이 순서대로 정점 배열을 순회하면서, 아직 표시되지 않은 정점에 대해 전치 그래프에서 dfs를 실행하여 도달 가능한 모든 정점에 새 연결 요소의 번호를 표시합니다.

이렇게 하면 연결 요소의 번호가 위상 정렬된 순서가 됩니다.