강한연결요소(SCC, Strongly Connected Component), 코사라주, 타잔

개념

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;
}