131. Kosaraju's Algorithm

먼저 임의의 정점 $v$가 주어졌을 때 $v$를 포함하는 SCC 하나를 구하는 방법을 살펴본다.

$v$에서 이동할 수 있는 정점들과 $v$로 이동할 수 있는 정점들의 교집합을 구하면 그 집합에 속한 정점들이 한 SCC로 묶이게 된다. $v$에서 이동할 수 있는 정점들은 DFS로 쉽게 구할 수 있고, $v$로 이동할 수 있는 정점들은 간선들을 전부 뒤집은 다음 DFS를 실행하면 구할 수 있다. 두 번의 DFS에서 모두 방문한 정점들은 $v$와 같은 SCC에 속한다.

 

따라서 다음과 같은 방법으로 그래프의 SCC를 전부 구할 수 있다. (그래프에 존재하는 정점의 수가 $n$이라고 가정한다.)

    1. 아직 SCC로 묶이지 않은 정점 중 하나를 선택해서 그 정점에서 DFS를 실행한다.

    2. 그래프의 간선을 전부 뒤집고, 1번에서 DFS를 시작한 정점에서 다시 DFS를 실행한다. (이를 흔히 역방향 DFS라고 한다.)

    3. 두 번의 DFS에서 모두 방문한 정점들을 하나의 SCC로 묶는다.

    4. 모든 정점이 SCC로 묶일 때까지 위의 과정을 반복한다.

 

이 방법은 꽤 간단하지만 시간복잡도가 $O(n^2)$이라는 큰 단점이 존재한다. 그래서 $n$이 십만 단위로 커지는 문제에서는 거의 써먹을 수가 없다. $n$이 큰 문제 중에서는 아래의 연습문제에 소개한 이 문제가 거의 유일하게 이 양방향 DFS 방법이 먹힌다.

---

코사라주 알고리즘(Kosaraju's Algorithm)은 위에 나온 양방향 DFS를 개선한 형태로 되어 있으며 다음과 같은 방법으로 작동한다.

    1. 아직 방문하지 않은 정점 중 하나를 선택해서 그 정점에서 DFS를 실행하는 과정을 반복한다. 이때 각 정점이 DFS를 종료한 시점을 저장한다.

    2. 그래프의 간선을 전부 뒤집고, 모든 정점을 방문하지 않은 상태로 바꾼다.

    3. DFS를 종료한 시점이 늦은 정점부터 차례로 확인하면서 아직 방문하지 않은 정점이 나왔을 경우 그 정점에서 DFS를 실행한다. 각각의 DFS에서 처음으로 방문한 정점들은 같은 SCC에 속한다.

 

앞 글에서 나온 그래프로 예시를 들면 다음과 같다. 편의상 정점의 방문 순서는 알파벳 순이라고 하자.

먼저 정점 $\text{A}$를 아직 방문하지 않았으므로 정점 $\text{A}$에서 DFS를 시작한다. 간선을 따라서 정점 $\text{B}$, $\text{E}$, $\text{C}$, $\text{G}$를 차례로 방문하고, 뒤로 돌아가서 정점 $\text{H}$, $\text{D}$를 방문하고, 뒤로 돌아가서 정점 $\text{I}$를 방문한다. 여기서 DFS를 종료한 순서는 $\text{G}$ - $\text{C}$ - $\text{E}$ - $\text{B}$ - $\text{D}$ - $\text{H}$ - $\text{I}$ - $\text{A}$이다.

다음으로 방문하지 않은 정점은 $\text{F}$이고, 정점 $\text{F}$에서 DFS를 시작한다.

모든 정점을 방문했으므로, 방문 상태를 모두 초기화하고 간선을 모두 뒤집는다.

이제 DFS 종료 순서가 늦은 정점부터 차례로 DFS를 실행한다. 먼저 정점 $\text{F}$에서 DFS를 실행한다. 여기서 처음 방문하는 정점은 $\text{F}$ 하나밖에 없다. 따라서 정점 $\text{F}$가 SCC로 묶인다.

다음으로 DFS 종료 순서가 늦은 정점은 $\text{A}$이다. 여기서 DFS를 시작하면 정점 $\text{D}$, $\text{H}$를 새로 방문하게 되며, 이 세 정점이 한 SCC에 묶인다.

다음으로 정점 $\text{I}$에서 DFS를 시작한다. 여기서 새로 방문하는 정점은 $\text{I}$ 하나고, 이 정점이 SCC로 묶인다.

다음으로 DFS 종료 순서가 늦은 정점인 $\text{H}$와 $\text{D}$는 이미 방문했으므로 그냥 넘어간다. 그 다음은 정점 $\text{B}$이고, 아직 방문하지 않은 정점이므로 여기서 DFS를 시작하면 정점 $\text{G}$, $\text{C}$, $\text{E}$를 차례로 방문하고 DFS가 종료된다. 이 네 정점이 SCC로 묶인다.

나머지 정점들은 이미 방문했으므로 DFS를 실행하지 않는다.

최종적으로 $4$개의 SCC가 생겼다. 앞 글에서 보인 것과 같다.

---

이 알고리즘의 정당성 증명은 다음과 같은 방법으로 할 수 있다.

간선을 뒤집은 다음 SCC를 묶는 과정에서 DFS를 시작한 정점 하나를 골라서 $u$라고 하고, 그 DFS에서 처음으로 방문하면서 $u$와 같은 SCC로 묶인 정점 하나를 골라서 $v$라고 하면 다음의 조건이 성립한다.

• 역방향 DFS에서 $u$에서 $v$로 가는 경로가 존재하므로 정방향 DFS에서는 $v$에서 $u$로 가는 경로가 존재한다.
• 정방향 DFS를 종료한 시점이 $u$가 $v$보다 늦으므로 정점 $v$의 방문이 완료된 다음 $u$의 방문이 완료되어야 한다.
• 정방향 DFS에서 $u$에서 $v$로 가는 경로가 존재하지 않을 경우, $u$를 먼저 방문하면 $u$의 방문이 완료된 다음 $v$의 방문이 완료되는 상황이 되므로 정방향 DFS에서 $v$를 먼저 방문해야 하는데 이 경우 $v$에서 탐색을 진행하는 도중 $u$를 방문하게 되고, 마찬가지로 $u$의 방문이 $v$의 방문보다 먼저 완료된다. 따라서 처음의 가정이 모순이고 $u$에서 $v$로 가는 경로가 존재한다.
• $u$에서 $v$로 가는 경로가 존재하고 $v$에서 $u$로 가는 경로가 존재하므로 $u$와 $v$는 같은 SCC에 속한다. 또한 $u$에서 DFS를 시작하면 $u$와 같은 SCC에 있는 모든 정점이 위의 논리로 한번에 묶여야 하므로 $u$와 같은 SCC에 속하는 정점이 $u$에서 DFS를 시작했을 때 SCC로 묶이지 않는 상황은 발생하지 않는다. 따라서 서로 다른 DFS에서 묶인 정점들은 서로 다른 SCC에 속한다.

구현은 다음과 같다. 두 번의 DFS를 통해 SCC를 전부 구한다. DFS를 완료한 순서대로 정점을 스택에 추가하면 스택에서 정점을 하나씩 빼면서 역방향 DFS를 실행할 수 있다.

#import<bits/stdc++.h>
using namespace std;
int vi[100005];
vector<int>e1[100005], e2[100005], scc[100005];
stack<int>S;
void dfs1(int u) // 정방향 DFS
{
    vi[u] = 1;
    for(auto &v: e1[u])
    {
        if(!vi[v])dfs1(v);
    }
    S.push(u);
}
void dfs2(int k, int u) // 역방향 DFS
{
    vi[u] = 1;
    scc[k].push_back(u);
    for(auto &v: e2[u])
    {
        if(!vi[v])dfs2(k, v);
    }
}
int main()
{
    int m, n, x, y;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        e1[x].push_back(y); // 정방향 간선
        e2[y].push_back(x); // 역방향 간선
    }
    for(int i = 1; i <= n; i++)
    {
        if(!vi[i])dfs1(i);
    }
    fill(vi + 1, vi + n + 1, 0);
    for(; S.size(); S.pop())
    {
        x = S.top();
        if(!vi[x])dfs2(x, x);
    }
}

 

[연습문제]

 

BOJ 26146. 즉흥 여행 (Easy) (Gold I)

문제에서 모든 SCC를 요구하는 것이 아니기 때문에 양방향 DFS로 푸는 것이 가능하다. 난이도 투표를 보면 Gold를 매긴 기여가 꽤 보이는데, 코사라주 알고리즘이나 타잔 알고리즘의 기본 티어가 Platinum V로 책정되어 있을 뿐 SCC라는 개념만 이해하는 건 훨씬 더 쉽기 때문에 오히려 적절하다.

 

BOJ 2150. Strongly Connected Component (Platinum V) [샘플 코드]

그래프의 SCC를 모두 구하는 기본 문제이다.

 

BOJ 26157. 즉흥 여행 (Hard) (Platinum III)

이번에는 SCC를 다 구하고, 위상 정렬 비슷한 걸 하면 되는데 위상 정렬을 직접 할 필요는 없고, SCC끼리 묶은 그래프에서 진입 차수가 $0$인 SCC가 $1$개인지 확인하는 방식으로 풀면 된다.