SCC

Strongly Connected Component의 약자로

번역하면 강한 연결 요소, 강연결 요소로 불린다.

유향 그래프에서 모든 정점이 모든 다른 정점에 도달 가능한 경우, 그래프는 "강하게 연결되었다" 또는 "상호연결되었다" 라고한다. SCC의 경우 부분 그래프의 모든 정점이 강하게 연결된 임의의 유향 그래프의 분할이다.

DFS 기반 선형 시간 알고리즘

- 깊이 우선 탐색을 기반으로 하는 몇가지 알고리즘들은 선형 시간에 SCC를 계산할 수 있다.

• 코사라주의 알고리즘
• 타잔의 강한 연결 요소 알고리즘
• 경로기반 강한 요소 알고리즘

도달 가능성 기반 알고리즘

- 도달 가능성 쿼리를 기반으로 한 분할 정복 접근 방식의 알고리즘. 시간복잡도는 O(n log n) 으로 기존 방식보다 크지만 병렬화 되기가 더 쉽다.

아래는 백준 2150번 <Strongly Connected Component>의 풀이 코드이다. (작성자가 만든 풀이 임으로 정석적인 방식이 아닐 수 있음)

#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 100100;

vector<int> Ans[MAX_N];
vector<int> Ed[MAX_N], Ed_R[MAX_N];
stack<int> st;
int VST[MAX_N];

void dfs(int n){
    VST[n] = 1;

    for (int a : Ed[n]){
        if (VST[a]==1) continue;

        VST[n] = 1;
        dfs(a);
    }

    st.push(n);
}

void solve(int n, int ct){
    VST[n] = 2;

    for (int a : Ed_R[n]){
        if (VST[a]==2) continue;

        VST[n] = 2;
        solve(a, ct);
    }

    Ans[ct].push_back(n);
}

int main(){
    int v, e;
    scanf("%d%d", &v, &e);

    for (int i=0; i<e; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        Ed[a].push_back(b);
        Ed_R[b].push_back(a);
    }

    for (int i=1; i<=v; i++){
        if (VST[i]==1) continue;
        else dfs(i);
    }

    int ct=0;
    while (!st.empty()){
        int a = st.top(); st.pop();
        if (VST[a] == 2) continue;

        solve(a, ct);
        ct++;
    }

    printf("%d\n", ct);

    for (int i=0; i<ct; i++){
        sort(Ans[i].begin(), Ans[i].end());
    }

    sort(Ans, Ans+ct);

    for (int i=0; i<ct; i++){
        for (int j : Ans[i]){
            printf("%d ", j);
        } printf("-1\n");
    }
}