[Graph] SCC(Strongly Connected Components) 강한 결합 요소(1)

Strongly Connected : 모든 정점에서 정점으로 이동할 수 있다.
SCC : 그래프를 Strongly Connected 되게 나누는 것이다.

하나의 SCC에서 두 정점 u,v를 선택하면 u에서 v로 이동가능하고 v에서 u로 이동할 수 있는 가장 큰 집합을 만드는 것이다. 간단하게 말하면 사이클이 포함된 그래프는 위상정렬이 불가능하다. 하지만 scc를 수행하면 사이클을 묶은 큰 노드들이 되고 scc로 묶인 그룹 간에는 위상정렬이 가능하게 된다.

 

SCC를 구하는 방법으로는 코사라주알고리즘과 타잔 알고리즘이 있다

먼저 코사라주 알고리즘 부터 살펴보자

Kosarju’s algorithm

1. 첫 번째 dfs를 하면서 정점에 후위순회 번호를 매긴다. 그 다음 후위 순회 결과를 뒤집어준다.

2. 두 번째 dfs는 1에서 나온 결과순서대로 역방향 간선의 그래프에 대해 실행한다.

3. 두 번째 dfs마다 나온 정점들이 하나의 SCC를 이루는 것이다.

 

코드는 https://www.acmicpc.net/problem/4196 기준으로 작성했다.

 

#include <iostream>
#include <vector>
#include <list>
using namespace std;
#define N 100001
vector<int>adj[N];
vector<int>rev[N];
int indegree[N];
int visit[N];
void dfs1(int now, list<int>& result) {
    visit[now] = 1;
    for (int next : adj[now]) {
        if (!visit[next]) {
            dfs1(next, result);
        }
    }
    result.push_front(now);
}
void dfs2(int now) {
    visit[now] = 2;
    for (int next : adj[now]) {
        if (visit[next] == 1) {
            dfs2(next);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> n >> m;
        for (int i = 1; i <= n; ++i) {
            adj[i].clear(); visit[i] = 0; rev[i].clear();
        }
        for (int i = 0, u, v; i < m; ++i) {
            cin >> u >> v;
            adj[u].push_back(v);
            rev[v].push_back(u);
        }
        list<int>result;
        for (int i = 1; i <= n; ++i) {
            if (!visit[i]) dfs1(i, result);
        }

        int ans = 0;
        for (int i : result) {
            if (visit[i] == 1) {
                dfs2(i); ++ans;
            }
        }
        cout << ans << '\n';
    }
}

main, dfs1, dfs2 함수를 각각 살펴보면

main은 그래프를 초기화하고 입력을 받아서 그래프와 전치그래프를 만든다. 그 다음 dfs1의 후위순회 방문순서를 저장하기 위해 list형태로 result를 선언하고 dfs1의 인자로 넘겨준다. (단순 후위순회결과라면 뒤집어야하는데 dfs1 에서 list의 push_front를 통해 방문순서를 저장하였기 때문에 따로 뒤집는 과정이 없어도 됨)

그 다음은 result에 있는 순서대로 dfs2를 호출하며 dfs2가 호출될 때마다 하나의 scc를 찾는 것이므로 답을 증가시켜주었다.

 

이해

dfs1의 첫번째 단계에서 해주는 것을 살펴보면 후위순회를 하고 결과를 뒤집는데 이것을 통해 특정 노드들의 순서를 보장하게 해준다. 그 다음 두 번째 단계를 살펴보자. 서로 다른 SCC a 와 b가 있고 a 안쪽에는 u라는 정점이 있고 b에는 v라는 정점이 있다고 하자. 그리고 첫 번째 단계로부터 a ->  b 이라고 가정하면 첫 번째 후위순회를 뒤집은 곳에는 u 다음 v가 오게 된다. 그런데 전치그래프에서 dfs2를 실행한다. 즉 u가 속한 어떤 SCC의 어떤 정점도 SCC b로는 넘어갈 수가 없고 dfs1의 결과에는 u는 항상 v보다 앞에 오기 때문에 dfs2는 항상 u부터 실행하게 된다.