SCC 강한 연결 요소: Kosaraju와 Tarjan 알고리즘

SCC는 방향 그래프에서 서로 도달 가능한 정점들을 하나의 강한 연결 요소로 묶는 개념입니다.

SCC를 찾으면 그래프 안의 사이클 구조를 컴포넌트 단위로 압축할 수 있고, 압축된 그래프는 DAG가 되어 위상정렬이나 DP를 적용하기 쉬워집니다.

 

핵심 정리

SCC 안의 정점들은 서로 오갈 수 있으므로 하나의 컴포넌트처럼 다룰 수 있습니다. Kosaraju 알고리즘은 원래 그래프에서 DFS 종료 순서를 구한 뒤, 간선을 뒤집은 그래프에서 그 순서대로 다시 DFS를 수행해 SCC를 찾습니다. Tarjan 알고리즘은 한 번의 DFS 흐름에서 방문 순서와 low-link 값을 이용해 SCC의 루트를 판별합니다. 구현 난이도는 다르지만 둘 다 방향 그래프의 사이클 묶음을 찾아 압축 그래프를 만드는 데 사용됩니다.

• SCC 내부의 임의의 두 정점은 서로 도달할 수 있습니다.
• SCC를 하나의 정점으로 압축하면 컴포넌트 그래프를 만들 수 있습니다.
• 압축된 SCC 그래프는 사이클이 없는 DAG가 됩니다.
• Kosaraju는 DFS를 두 번 사용하고 역방향 그래프가 필요합니다.
• 첫 DFS의 종료 순서는 두 번째 DFS의 방문 순서를 정하는 데 쓰입니다.
• Tarjan은 DFS 번호와 low-link 값을 이용해 SCC를 한 번의 DFS에서 찾습니다.
• SCC 압축은 2-SAT, ATM, 그래프 DP 같은 문제의 전처리로 자주 등장합니다.
• SCC를 찾은 뒤에는 컴포넌트 번호와 컴포넌트 간 간선을 따로 관리해야 합니다.

원문은 Kosaraju 구현과 개념 설명으로 이어지므로, SCC를 단순히 사이클 찾기가 아니라 방향 그래프를 DAG로 압축하는 전처리로 이해하도록 보강했습니다.

이어서 볼 글

• 백준 ATM 풀이: SCC 압축과 DAG 최장 경로 - SCC를 압축한 뒤 DAG에서 DP를 적용하는 대표 응용이다.

 

개념

SCC는 방향그래프 내에서 서브사이클을 이루는 집단들을 의미한다. 따라서 개념적으로는 강한연결요소라는 용어보다 강한연결집합이라는 용어가 더 적절해보이긴한다.

자세한 설명은 여기, 여기, 여기를 참조하면 개념에 대해서 어렵지 않게 파악 가능하다.

동작하는 원리에 대해 궁금하면 여기에 설명이 잘 나와있다.

활용도와 의의에 대해서는 여기에 잘 나와있다.

SCC를 구하는 알고리즘에는 크게 코사라주와 타잔이 있다.

코사라주(Kosaraju) 알고리즘

코사라주는 DFS두번 돌리면서 구하는 방법이고 여기, 여기를 보면 설명이 잘 돼있어서 쉽게 이해 가능하다. 

구현도 그냥 이해한 대로 술술 하면 되는 수준이었다.

왜 그런지 증명은 정확히 모르겠고 HOW는 파악이 어렵지 않다.

아래는 내가 직접 구현해본 코드이고, 이 문제의 답안이기도 하다.

dfs함수에서 마지막에 스택push하는 걸 보면 위상정렬개념이 들어간다는 사실을 알 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vvi = vector<vi>;
#define endl '\n';
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0);
 
    int V, E; cin >> V >> E;
    vvi adj_list(V + 1), adj_list2(V + 1);
    REP(i, E) {
        int a, b; cin >> a >> b;
        adj_list[a].push_back(b);
        adj_list2[b].push_back(a); // 역방향
    }
 
    // step1. dfs로 방문하며 말단부터 stack push
    vi visit(V + 1); stack<int> S;
    function<void(int n)> dfs = [&](int n) {
        if (visit[n]) return;
        visit[n] = 1;
        for (auto a : adj_list[n]) dfs(a);
        S.push(n);
    };
    REP1(i, V) if (visit[i] == 0) dfs(i);
 
    // step2. stack에서 꺼내면서
    // 역방향으로 접근가능한 정점들을 SCC로 판정
    visit.clear(); visit.resize(V + 1); vvi ans;
    while (S.size()) {
        int n = S.top(); S.pop();
        if (visit[n]) continue;
        vi ans2;
        function<void(int n)> dfs = [&](int n) {
            if (visit[n]) return;
            visit[n] = 1;
            ans2.push_back(n);
            for (auto a : adj_list2[n])    dfs(a);
        };
        dfs(n);
        sort(ALL(ans2));
        ans.push_back(ans2);
    }
    sort(ALL(ans));
    cout << ans.size() << endl;
    REP(i, SZ(ans))    {
        REP(j, SZ(ans[i])) cout << ans[i][j] << ' ';
        cout << -1 << endl;
    }
 
    return 0;
}

타잔(Tarjan) 알고리즘

타잔 알고리즘은 생각보다 이해하기가 빡시다. 한가지 알아둘 것은 타잔 알고리즘이 SCC구할때 쓰는 알고리즘만 칭하는게 아니라, 여기서 쓰는 테크닉과 비슷하면 타잔이라고 부르는 것 같다는 점이다(타잔류?). 이건 확인은 필요

타잔의 경우, 결과값으로 SCC위상정렬까지 얻을 수 있어서, 이후 활용도에서 더 편하다.

타잔 알고리즘을 이해하려면, 먼저 트리 간선(tree edge), 순방향 간선(forward edge),역방향 간선(backward edge),교차 간선(cross edge)등 그래프 간선의 종류를 이해해야 한다.

그다음 단절선에 대한 이해를 해야한다. 그다음 여기 설명을 보면 이해하고 구현하기 좋다.

SCC타잔 알고리즘이 단절선 로직과 다른점은 다음과 같다.

1. 단절선 로직은 자식트리중 하나라도 현재간선보다 위로 못올라가면 바로, 단절선으로 판정하지만 SCC타잔에서는 전체 자식트리를 다 보고나서, 모든  자식트리가 현재간선보다 위로 못올라가면 SCC로 판정한다.

2. 단절선 로직과 다르게 스택을 운용하며, 처음 진입시 스택에 넣고 위의 1번 SCC판정조건이 만족되면 현재 정점까지 팝한다.

3. 단절선 로직은 visit배열만 사용하는데 반해서, SCC타잔은 finish배열도 추가적으로 사용한다. (물론 두 알고리즘 모두  visit배열대신 ord로 대체는 가능)

4. 단절선 로직은 tree-edge, back-edge만 고려하는데 반해서 SCC타잔은 추가적으로 cross-edge도 고려한다. (forward-edge는 둘다 무시)

단절선 코드를 변경해서 내가 구현해본 코드는 다음과 같다. 위와 같은 문제에 대한 답이기도 하다.

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vvi = vector<vi>;
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int V, E; cin >> V >> E;
    vvi adj_list(V + 1);
    REP(i, E)
    {
        int A, B; cin >> A >> B;
        adj_list[A].push_back(B);
    }
    vvi ans;
    stack<int> S;
    //아래에서 visit는 ord와 통합가능하지만, 가독성을 위해 남겨둠
    vi visit(V + 1), ord(V + 1), parent(V + 1); int g_ix = 0;
    // 코라사주나 단절선 구하는것과 다르게 finish 운영해줌
    // 일반적으로 finish배열이 dfs리턴할때 true해주는것과 다르게
    // SCC분리가 끝났음을 의미
    vi finish(V + 1);
    function<int(int)> dfs = [&](int n)-> int  // low를 리턴
    {
        visit[n] = 1;
        ord[n] = ++g_ix;
        int low = ord[n];
        S.push(n);  // 스택에 먼저 푸시
        for (auto adj : adj_list[n])
        {
            //if (adj == par) continue;  // SCC는 방향그래프로 주어지므로 parent개념은 없다.
            if (visit[adj] == 0)  // tree edge 의 경우
            {
                int r = dfs(adj);
                // 단절점 로직의 경우 여기서 자식트리중 하나라도 자신위로 올라가지 못하면 단절점으로 판정하지만
                // SCC 타잔에서는 그러한 로직은 없고, 아래에 result == ord[n] 으로
                // 자신포함 자식트리중 도달가능한 가장 높은 정점이 자신일 경우 SCC 추출하는 로직으로 바뀐다.
                // if (r > ord[n]) ans.insert({ min(n,adj), max(n,adj) });
                low = min(low, r);
            }
            // 방문은 했으나 아직 SCC로 추출되지는 않은 이웃
            else if (finish[adj]==0)  // back edge 또는 cross edge의 일부
                low = min(low, ord[adj]);  // 접근가능한 백정점 순서로 업데이트
        }
        // 자신포함 자식트리중 도달가능한 가장 높은 정점이 자신일 경우 SCC 추출
        if (low == ord[n])
        {
            vi scc;
            while(S.size())
            {
                int a = S.top(); S.pop();
                scc.push_back(a);
                finish[a] = 1;
                if (a == n) break;
            }
            sort(scc.begin(), scc.end());
            ans.push_back(scc);
        }
        
        return low;
    };
    REP1(i, V)if (visit[i] == 0)dfs(i);
    sort(ans.begin(), ans.end());
    cout << (int)ans.size() << '\n';;
    for(auto a:ans)
    {
        for (auto b : a) cout << b << ' ';
        cout << -1 << '\n';;
    }
    return 0;
}