132. Tarjan's Algorithm

타잔 알고리즘(Tarjan's Algorithm)은 그래프의 SCC를 전부 구하는 또 다른 알고리즘으로, 다음과 같은 방법으로 작동한다.

    1. 아직 방문하지 않은 정점 하나를 골라 그 정점에서 DFS를 실행한다.

    2. 새로운 정점을 방문할 때마다 그 정점의 방문 순서를 저장한다. 이를 우선순위(값이 작을수록 높음)로 간주하고, 정점마다 그 정점에서 도달할 수 있는 정점들의 우선순위 값 중 가장 높은 것을 저장한다. 이때 이미 SCC로 묶인 정점의 우선순위는 무시한다.

    3. 어떤 정점의 DFS가 종료될 때, 그 정점에서 도달할 수 있는 정점들 중 우선순위가 가장 높은 정점이 자신일 경우 스택에 쌓인 정점을 자신이 나올 때까지 전부 뽑고, 그 정점들을 하나의 SCC로 묶는다.

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

설명이 다소 난해하다. 그래서 이번에도 어김없이 예시 그래프가 등장한다. 이번에도 정점의 방문 순서는 알파벳 순이라고 하자.

정점 $\text{A}$에서 DFS를 시작하면 정점 $\text{B}$, $\text{E}$, $\text{C}$, $\text{G}$를 차례로 방문하면서 정점을 스택에 차례로 넣는다. 또한 이 정점들의 우선순위가 $1$부터 $5$까지 차례로 매겨진다.

정점 $\text{G}$에서 DFS를 계속 진행하면 정점 $\text{B}$를 방문하게 된다. $\text{B}$는 이미 방문한 정점이고, 우선순위가 $2$이므로 정점 $\text{G}$에서 도달할 수 있는 정점의 최고 우선순위는 $2$로 바뀐다. 이는 정점 $\text{C}$, $\text{E}$에도 적용된다.

정점 $\text{G}$의 탐색을 종료하고 정점 $\text{B}$까지 되돌아올 동안 스택에는 정점 $5$개가 그대로 존재한다. 다음으로 정점 $\text{B}$의 탐색을 종료하는데, $\text{B}$에서 갈 수 있는 정점들 중 우선순위가 가장 높은 정점이 $\text{B}$ 자신이므로 스택에 들어간 정점들을 $\text{B}$가 나올 때까지 뽑아서 하나의 SCC로 묶는다. 여기서는 정점 $\text{G}$, $\text{C}$, $\text{E}$, $\text{B}$가 묶인다.

다음으로 정점 $\text{A}$에서 $\text{H}$, $\text{D}$를 차례로 탐색한다.

정점 $\text{D}$에서 정점 $\text{A}$로 갈 수 있으므로 정점 $\text{D}$에서 갈 수 있는 정점의 최고 우선순위는 $1$이 된다. $\text{D}$에서 $\text{B}$로도 갈 수 있지만 $\text{B}$는 이미 SCC로 묶였으므로 무시한다.

정점 $\text{H}$에서 갈 수 있는 정점의 최고 우선순위도 $1$이 된다. 이후 정점 $\text{A}$로 돌아가서 정점 $\text{I}$ 쪽으로 탐색을 진행한다.

 

정점 $\text{I}$에서 갈 수 있는 정점은 $\text{C}$와 $\text{E}$인데 둘 다 이미 SCC로 묶였으므로 무시한다. 그렇다면 정점 $\text{I}$에서 갈 수 있는 정점들 중 우선순위가 가장 높은 정점은 $\text{I}$이고, 스택에서 정점 $\text{I}$를 꺼내서 SCC로 묶는다.

이제 정점 $\text{A}$에서 갈 수 있는 정점을 모두 방문했다. $\text{A}$에서 갈 수 있는 정점들 중 우선순위가 가장 높은 정점은 $\text{A}$이므로 스택에서 정점 $\text{D}$, $\text{H}$, $\text{A}$를 꺼내서 SCC로 묶는다.

아직 SCC로 묶지 않은 정점은 $\text{F}$가 있고, 여기서 DFS를 실행한다. 갈 수 있는 정점이 없어서 그냥 스택에 들어갔다가 바로 꺼내져서 SCC로 묶인다.

결과는 코사라주 알고리즘으로 SCC를 묶었을 때와 같다.

---

이 알고리즘의 정당성 증명은 다음과 같다.

• 어떤 정점 $u$에서 갈 수 있는 정점들 중 우선순위가 가장 높은 정점이 $u$ 자신이고, 스택에서 정점 $v$가 정점 $u$의 바로 위에 있을 경우 $v$에서 갈 수 있는 정점들 중 우선순위가 $u$보다 높은 정점은 존재하지 않는다. 그런 정점이 존재할 경우 $u$에서 갈 수 있는 정점들 중 우선순위가 가장 높은 정점이 $u$라는 사실과 모순이 된다.
• 따라서 스택에 존재하는 정점들에 대해서 각 정점에서 갈 수 있는 정점들의 최고 우선순위는 스택 위쪽으로 갈수록 같거나 낮아진다.
• 만약 $v$에서 갈 수 있는 정점들의 최고 우선순위가 $u$보다 낮다면, 비둘기집의 원리에 의해 스택에서 $u$의 위쪽에 있는 정점들 중 갈 수 있는 최고 우선순위의 정점이 자신이 되는 정점이 하나 이상 존재해야 한다. 그렇다면 그 정점은 이미 스택에서 빠지고 SCC로 묶여야 하는데, 그 정점이 현재 스택에 있으므로 그런 상황은 발생할 수 없다.
• 따라서 $v$에서 갈 수 있는 정점들 중 우선순위가 가장 높은 정점은 $u$이고, 이를 재귀적으로 확장하면 스택에서 $u$보다 위에 있는 각 정점에서 갈 수 있는 정점들 중 우선순위가 가장 높은 정점은 전부 $u$가 된다. 즉 그 정점들 전부에서 $u$로 가는 경로가 존재한다.
• $u$에서 $v$로 가는 경로가 존재하지 않을 경우, $u$의 탐색이 종료된 다음 $u$의 이전 정점들로 되돌아가서 거기서 $v$를 탐색해야 한다. 하지만 $u$의 탐색이 종료될 때 $v$가 이미 스택에 존재하므로 이런 상황은 발생할 수 없다. 따라서 $u$에서 $v$로 가는 경로가 존재하며, 이를 재귀적으로 확장하면 $u$에서 스택에서 $u$보다 위에 있는 정점들로 가는 경로가 전부 존재한다.
• 이상을 종합하면 스택에서 $u$의 위에 존재하는 정점들은 $u$와 같은 SCC에 속한다.
• 스택에서 $u$의 아래에 존재하는 정점들은 $u$에서 가는 경로가 존재하지 않으므로 서로 다른 SCC에 속한다.

구현은 다음과 같다. [샘플 코드]

#import<bits/stdc++.h>
using namespace std;
int c, v1[100005], v2[100005];
vector<int>e[100005];
stack<int>S;
int dfs(int u)
{
    int minc = v1[u] = ++c;
    S.push(u);
    for(auto &v: e[u])
    {
        if(!v1[v])minc = min(minc, dfs(v));
        else if(!v2[v])minc = min(minc, v1[v]);
    }
    if(minc == v1[u])
    {
        for(;;)
        {
            int x = S.top();
            S.pop();
            v2[x] = minc;
            if(x == u)break;
        }
    }
    return minc;
}
int main()
{
    int m, n, x, y;
    cin >> n >> m;
    for(int i = 1; i <= m;i++)
    {
        cin >> x >> y;
        e[x].push_back(y);
    }
    for(int i = 1; i <= n; i++)
    {
        if(!v1[i])dfs(i);
    }
}

[연습문제]

 

BOJ 25488. 토큰 (Platinum IV)

두 상태에서 각각의 SCC에 존재하는 토큰의 수가 변하지 않아야 미션을 수행할 수 있다.

 

BOJ 13929. British Menu (Platinum I)

그래프 압축을 하고 DAG DP로 푸는 문제이다. 모든 SCC의 크기가 $5$ 이하이므로 한 SCC 안에서 거칠 수 있는 정점의 최대 개수는 SCC 안의 경로를 전부 탐색하는 방식으로 구해도 되고, 다른 SCC로 전이를 잘 해 주면 된다. 이런 유형의 문제도 가끔씩 등장하므로 참고하면 좋다.