강한 연결 요소 (SCC) - 타잔 알고리즘

[백준 2150] Strongly Connected Component C++

 

학교 알고리즘 수업 때 코사라주 알고리즘을 활용한 SCC풀이법을 배웠다.

 

하지만 구글링을 해보니 코사라주 알고리즘보다는 타잔 알고리즘이 구현이 어렵지만 활용도가 더 높다고 해서 공부해 보았다.

 

 

타잔 알고리즘

 

 

1번 정점에서 dfs를 시작해 2, 3, 4번 정점을 순서대로 방문했다고 하자.

타잔 알고리즘에서는 방문할 때마다 임의의 stack에 방문 정점을 저장한다.

 

4번 정점을 방문했을 때 4번에서 방문 가능한 가장 높은 정점은 2번이다.

따라서 ret = 2가 되고 2번으로 되돌아가게 된다.

2번에 되돌아 왔을 때 자신의 방문 번호와 ret이 같으므로 stack의 top이 자신의 번호인 2가 될 때까지 pop을 한다.

stack에서 pop된 정점들은 모두 같은 SCC가 된다. => 2, 3, 4는 1번 SCC가 된다.

 

1번 정점으로 되돌아가서 연결된 5번 정점을 타고 6번까지 내려간다.

6번은 4번정점으로 갈 수 있지만 4번 정점은 방문한 적이 있고 SCC를 이루고 있기 때문에 해당 간선은 무시된다.

 

6에서 갈 수 있는 가장 높은 정점은 5번이 되고 5번으로 돌아가서 stack에 쌓인 원소를 제거하면서 SCC를 만들어 준다.

=> 5, 6은 2번 SCC가 된다.

 

마지막으로 1번으로 되돌아가고 stack에 있는 1번 정점만이 3번 SCC가 된다.

 

 

타잔 알고리즘을 통해서 SCC를 구하는 방법을 예시를 통해서 살펴보았다.

 

모든 정점을 탐색하고 정점에 달려있는 간선의 개수만큼 추가로 탐색하므로

시간 복잡도는 O(|V| + |E|)가 된다.

---

 

코드에서 새로운 SCC가 생기는 시점은 항상 scc함수가 종료하기 직전이다.

이와 같은 속성 때문에 각 SCC는 위상 정렬의 역순으로 번호가 매겨짐을 알 수 있다.

따라서 scc함수가 늦게 종료하는 정점부터 배열한다면 scc 그래프의 위상 정렬 결과를 알 수 있게 된다!

 

---

코드

vector<int> Vertex[20002];
int SCCnum[20002];
vector<int> stk;
int discovered[20002];
 
int sccCounter, vertexCounter;
 
 
int SCC(int now){
    int ret = discovered[now] = vertexCounter++;
    stk.push_back(now);
    
    for(int i = 0; i < Vertex[now].size(); i++){
        int next = Vertex[now][i];
        
        if(discovered[next] == -1){
            ret = min(ret, SCC(next));
        }
        else if(SCCnum[next] == -1){
            ret = min(ret, discovered[next]);
        }
    }
    
    if(ret == discovered[now]){
        while(true){
            int temp = stk.back();
            stk.pop_back();
            SCCnum[temp] = sccCounter;
            if(temp == now) break;
        }
        sccCounter++;
    }
    
    return ret;
}

 

위 코드는 2-SAT-3 문제 풀이에서 SCC를 구하기 위해 타잔 알고리즘을 사용한 코드이다.

 

다음 포스팅은 2-SAT 문제를 포스팅하겠다..

 

지금까지 풀어본 문제 중 제일 어려웠던 문제!