[알고리즘] #13. SCC(코사라주, 타잔) 알고리즘

#SCC(Strongly Connected Component): 강한 연결 요소

유향 그래프에서 임의의 두 정점 A, B에 대해 항상 A->B로 가는 경로가 존재하는 정점 그룹.

+ 즉 SCC안의 어떤 두 정점을 선택해도 서로 도달할 수 있는 경로가 존재한다.

+ SCC는 항상 최대로 정의된다.

+ 즉 SCC는 집합 내의 정점들이 서로 왕복 가능한 최대 크기의 집합이다.

* 코사라주 알고리즘, 타잔 알고리즘은 모두 DFS(깊이 우선 탐색)를 기반으로 동작한다.

 

#코사라주 알고리즘

주어진 그래프의 SCC(강한 연결 요소)를 찾기 위한 알고리즘

즉, 그래프 A가 주어질때,

1. 그래프 A에 대해 DFS를 수행하며, 방문하는 순서대로 스택 S에 삽입한다.

2. 그래프 A의 역방향 그래프 A'에 대해 스택 S에서 pop하는 순서대로 DFS(역방향)를 수행한다.

3. 2번 과정에서 역방향 DFS를 수행하며 탐색되는 정점을 같은 SCC로 묶고 스택 S가 빌때까지 반복한다.

 

##시간복잡도

2번의 DFS를 수행하므로 DFS와 같은 O(V + E)

 

ex)

코사라주 알고리즘을 수행할 그래프 A

그래프 A의 역방향 그래프 A'를 모델링 한다.

정점1에서 시작하여 DFS를 수행한다. 1->4->5까지 방문한후 호출한 DFS가 종료되어 정점5가 스택 S에 푸시된다.

이어 정점4에서 호출한 DFS가 종료되어 S에 푸시되고, 정점1에서 1->6->7->2까지 방문한후 정점2에서 호출한 DFS가

종료되어 정점2가 S에 푸시되고 이와같이 반복하여 해당 그림의 상태가 된다.

현재 스택 S에는 1 - 6 - 7 - 3 - 2 - 4 - 5 순서로 되어있고 현재 top은 1을 가리킨다.

역방향 그래프 A'에서 S의 top이 가리키는 1번정점에서 DFS를 수행한다. 해당 DFS는 1->5->4 순서로 탐색한후 종료된다. 이로서 정점 1,4,5는 같은 SCC를 이루게된다.

다음 S의 top이 가리키는 정점 6에서 DFS를 수행한다. 1번 정점은 이미 visited상태이므로 방문할 수 없으므로 DFS가 종료되고, 정점 6은 하나의 SCC를 이룬다.

그다음 S의 top이 가리키는 정점 7에서 DFS를 수행한다. visited상태인 정점6은 방문하지 않고, 정점 2, 3을 방문한후 해당 DFS가 종료되어 정점 2,3,7은 같은 SCC를 이루게 된다.

##코드

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstring>

#define MAX_V 10001

using namespace std;

vector<vector<int>> scc;
vector<vector<int>> eg;
vector<vector<int>> egR;
int visited[MAX_V];
//V: 정점개수, E: 간선개수, R: SCC개수
int V, E, R;
stack<int> s;

bool cmp(vector<int> x, vector<int> y) {
    return x[0] < y[0];
}
void dfs(int v) {
    visited[v] = true;
    for (int next : eg[v]) {
        if (visited[next])
            continue;
        dfs(next);
    }
    s.push(v);
    cout << v << " ";
}
void func(int v, int c) {
    visited[v] = true;
    scc[c].push_back(v);
    for (int next : egR[v]) {
        if (visited[next])
            continue;
        func(next, c);
    }
}
int main() {

    cin >> V >> E;
    eg.resize(V + 1);
    egR.resize(V + 1);
    int x, y;
    for (int i=0; i<E; ++i) {
        cin >> x >> y;
        eg[x].push_back(y);
        egR[y].push_back(x);
    }
    //dfs수행
    for (int i=1; i<=V; ++i) {
        if (visited[i])
            continue;
        dfs(i);
    }
    cout << '\n';
    //visited배열 0으로 초기화
    memset(visited, 0, sizeof(visited));
    //역방향 그래프에대해 dfs수행
    while (s.size()) {
        int here = s.top();
        s.pop();
        if (visited[here])
            continue;
        scc.resize(++R);
        func(here, R-1);
    }

    for (int i=0; i<R; ++i)
        sort(scc[i].begin(), scc[i].end());
    sort(scc.begin(), scc.end(), cmp);

    cout << R << '\n';
    for (int i=0; i<R; ++i) {
        for (int x : scc[i])
            cout << x << " ";
        cout << "-1" << '\n';
    }
}

// https://jason9319.tistory.com/98

 

 

 

#타잔 알고리즘

코사라주 알고리즘과는 달리 한번의 dfs탐색으로 SCC를 추출 가능한 알고리즘

+ 이해하기 매우 어려웠음ㅠ

그래프 A가 주어질때,

1. 일단 한 정점을 기준으로 DFS수행.

2. 방문하는 각 정점을 스택S에 push()하고, dfsn[]배열 값을 1씩 증가시켜준다.

   => 방문 순위가 낮을수록 정점의 dfsn값은 높아진다.

3. dfsn값이 -1이 아닌, 즉 방문했던 정점을 방문하면 해당 정점이 SCC로 추출되었는지 확인한다.

4. 추출되지 않은 정점이고, 자신과 자신의 자식정점이 도달할 수 있는 최대 정점이 자신이라면, 스택S에서 현재 정점이 나올때까지 pop()하여 같은 SCC로 묶는다.

 

코드를 보면서 이해하는게 좀 더 빠를듯?

##코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
 
using namespace std;
 
const int MAX = 10010;
 
// SCCtotal : SCC 개수, sn[i]: i가 속한 SCC의 번호
int V, E, cnt, dfsn[MAX], SCCtotal, sn[MAX];
vector<int> adj[MAX];
bool finished[MAX]; // SCC가 확정된 정점 판별
stack<int> s;
vector<vector<int>> SCC;
 
// SCC에 사용될 dfs
int dfs(int curr)
{
    dfsn[curr] = ++cnt; // dfsn 결정
    s.push(curr); // 스택에 자신을 push
 
    // 자신의 dfsn, 자식들의 결과나 dfsn 중 가장 작은 번호를 result에 저장
    int result = dfsn[curr];
    for (int next : adj[curr])
    {
        // 아직 방문하지 않은 이웃
        if (dfsn[next] == 0) {
            result = min(result, dfs(next));
        }
 
        // 방문은 했으나 아직 SCC로 추출되지는 않은 이웃
        else if (!finished[next]) {
            result = min(result, dfsn[next]);
        }
    }
 
    // 자신, 자신의 자손들이 도달 가능한 제일 높은 정점이 자신일 경우 SCC 추출
    if (result == dfsn[curr])
    {
        vector<int> curSCC;
        // 스택에서 자신이 나올 때까지 pop
        while (1)
        {
            int t = s.top();
            s.pop();
            curSCC.push_back(t);
            finished[t] = true;
            sn[t] = SCCtotal;
 
            if (t == curr)
                break;
        }
 
        // 출력을 위해 원소 정렬
        sort(curSCC.begin(), curSCC.end());
 
        // SCC에 현재 이루어진 SCC 정보 push_back
        SCC.push_back(curSCC);
        SCCtotal++; // SCC 개수 
    }
 
    return result;
}
 
int main() {
    // 그래프 정보 입력
    scanf("%d %d", &V, &E);
    for (int i = 0; i< E; i++) {
        int from, to;
        scanf("%d %d", &from, &to);
        adj[from].push_back(to);
    }
 
    // DFS를 하며 SCC 추출
    for (int i = 1; i <= V; i++)
        if (dfsn[i] == 0) {
            cout << "dfs: " << i << '\n';
            dfs(i);
        }
 
    // 출력을 위해 SCC들을 정렬
    sort(SCC.begin(), SCC.end());
 
    // SCC 개수
    printf("%d\n", SCCtotal);
 
    // 각 SCC 출력
    for (auto& currSCC : SCC)
    {
        for (int curr : currSCC)
            printf("%d ", curr);
 
        printf("-1\n");
    }
}
 

 

참고한 사이트

https://blog.naver.com/kks227/220802519976

강한 연결 요소(Strongly Connected Component) (수정: 2019-08-03)

https://www.crocus.co.kr/950

SCC(Strongly Connected Component)