[알고개념] 5. Strongly Connected Component

이 글은 https://blog.naver.com/kks227/220802519976 을 참고하여 작성하였습니다.

 

1. SCC의 개념

• SCC는 그래프 내의 모든 두 정점에 대해서 도달할 수 있는 경로가 존재하는 그래프를 의미한다.
• 아래 그래프에 대해서 {a, b, e}, {f, g}, {c, d, h}가 각각 하나의 SCC를 이룬다.
• SCC는 Maximal한 성질을 갖는다. 즉, 아래에서 c, d만 포함해도 경로가 존재한다는 성질은 만족되지만 h까지 포함해야 최대 크기의 SCC이기 때문에 반드시 h를 포함해야 한다.

 

2. 타잔 알고리즘

그래프에서 SCC를 찾는 알고리즘에는 코사라주 알고리즘과 타잔 알고리즘이 존재한다. 그 중에서 타잔 알고리즘을 알아보자.

1. 그래프의 각 컴포넌트에 대하여 DFS를 돌려서 DFS 트리를 생성하는데, 이 과정에서 SCC를 뽑아낼 것이다.
2. DFS로 방문한 순서 번호를 각 노드에 저장해두고, 스택에 쌓아둔다.
3. 이후 result에 자손들 중 도달할 수 있는 가장 높은 정점을 저장한다. 따라서 자신의 DFS 순서 번호, 방문하지 않은 자식들의 결과들 중 가장 작은 번호를 result에 저장한다.
4. 자신과 자손들 중 도달 가능한 제일 높은 정점이 자신이면 SCC 추출을 시작한다. (즉, 자신의 자손들이 자신의 조상으로 갈 수 있는 경우가 하나도 없는 경우를 의미한다.) 지금까지 쌓아둔 스택에서 자기 자신이 나올 때까지 pop을 진행한다. 이 과정에서 SCC로 추출된 노드는 finished 처리를 해주고, SCC 번호를 매겨준다. SCC가 모두 뽑히면 내부를 정렬하고 SCC를 담는 벡터에 저장한다. 

#include <bits/stdc++.h>

using namespace std;

int v, e;
vector<vector<int>> adj, SCC;

// dfsNum: DFS 순서 번호 / sccNum: SCC 속한 번호
vector<int> dfsNum, sccNum;
vector<bool> finished;
stack<int> st;

int dfsn = 0, sccn = 0;

int DFS_FindSCC(int curr) {
    dfsNum[curr] = ++dfsn;
    st.push(curr);

    // 자신의 dfsNum, 자식들의 결과, dfsn 중 가장 작은 번호를 result에 저장
    int result = dfsNum[curr];
    for (int next : adj[curr]) {
        // 방문하지 않은 자식
        if (dfsNum[next] == 0) result = min(result, DFS_FindSCC(next));
        // 방문한 자식 중 아직 SCC에 들어가지 않은 자식
        else if (!finished[next]) result = min(result, dfsNum[next]);
    }

    // 자신과 자손들 중 도달 가능한 제일 높은 정점이 자신이면 SCC 추출
    if (result == dfsNum[curr]) {
        vector<int> currSCC; // 현재 SCC
        
        // 스택에서 자신이 나올 떄까지 pop
        while (true) {
            int t = st.top();
            st.pop();
            currSCC.push_back(t);
            finished[t] = true;
            sccNum[t] = sccn;
            if (t == curr) break;
        }
        sort(currSCC.begin(), currSCC.end());
        SCC.push_back(currSCC);
        sccn++;
    }
    return result;
}

int main() {
    cin.tie(NULL);	cout.tie(NULL);	std::ios::sync_with_stdio(false);
 
    cin >> v >> e;
    adj.resize(v + 1);
    finished.resize(v + 1);
    dfsNum.resize(v + 1);
    sccNum.resize(v + 1);

    for (int i = 0; i < e; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
    }

    // DFS로 입력받은 후 방문하지 않은 모든 정점에 대해 DFS를 돌리며 SCC 찾기
    for (int i = 0; i < v; i++) {
        if (dfsNum[i] == 0) DFS_FindSCC(i);
    }
    sort(SCC.begin(), SCC.end());

    cout << sccn << "\n";
    for (auto& currSCC : SCC) {
        for (int curr : currSCC) {
            cout << curr + 1 << " ";
        }
        cout << -1 << "\n";
    }
}