강결합 컴포넌트 (Strongly Connected Component)

방향성 그래프에서 다음 조건을 만족하는 정점들의 집합을 강결합 컴포넌트 (SCC)라고 합니다.

1. SCC내의 임의의 두 정점 u, v사이의 u → v 경로와, v → u 경로가 항상 존재한다.

2. SCC내의 임의의 정점 u와, 외부의 임의의 정점 v 사이에, u → v 경로와, v → u 경로가 동시에 존재하는 경우는 없다.

즉, SCC는 내부의 모든 정점에서 내부의 다른 모든 정점으로 갈 수 있는 최대 그룹이라고 할 수 있습니다.

또한 모든 방향성 그래프는 한개 이상의 SCC들로 분리될 수 있습니다.

예를들어 이 그래프는 {1, 2, 4} , {3} , {5, 6} 이렇게 3개의 SCC들로 분리됩니다.

DFS를 사용해서 어떠한 그래프를 강결합 컴포넌트들로 분리할 수 있습니다. DFS를 사용해서 강결합 컴포넌트를 분리하는 알고리즘인 Kosaraju's algorithm과 Tarjan's algorithm을 알아보겠습니다.

---

DFS 트리와 간선의 분류

본격적으로 SCC분리 알고리즘을 알아보기 전에 먼저 DFS 트리라는 개념을 알아야 합니다. DFS 트리란 어떠한 그래프에서 DFS를 하는 과정을 트리로 나타낸것입니다. 예를 들어 위의 그래프에서 1번 노드를 출발지로 DFS를 하게되면 다음과 같은 트리가 만들어집니다.

여기서 discovery time이란 그 정점을 방문한 시간이고, finish time은 그 정점의 모든 자식들을 방문하고 그 정점을 빠져나가는 시간입니다.

아래에서는 편의상 정점 u의 discovery time을 dt[u]라 하고, finish time을 ft[u]라 하겠습니다.

이러한 DFS를 통해 그래프의 간선들을 다음과 같이 분류할 수 있습니다.

1. tree edge

그래프의 간선들 중 DFS트리에 속하는 간선들입니다. 이 경우에 dt[u] < dt[v] 이고, ft[u] > ft[v] 입니다. 

2. back edge

그래프의 간선 (u → v)들 중에서, DFS트리에서 v가 u의 조상인 간선들입니다. 즉 DFS트리에서 거꾸로 조상한태 올라가는 간선입니다.

이 경우에 dt[u] > dt[v] 이고, ft[u] < ft[v] 입니다.

3. forward edge

그래프의 간선 (u → v)들 중에서, DFS트리에서 u가 v의 조상인데 tree edge에는 속하지 않는 간선들입니다. 

이 경우에 dt[u] < dt[v] 이고, ft[u] > ft[v]입니다

4. cross edge

위의 3가지 간선에 해당하지 않는 간선들입니다. 그래프의 간선 (u → v)들 중에서, DFS트리에서 u가 v의 조상도 아니고, v가 u의 조상도 아닌 경우

이 경우에 dt[u] > ft[v] 입니다.

모든 방향성 그래프의 간선들은 이 4가지중 하나에 속하게 됩니다. 위의 그래프의 간선들을 분류하면 다음과 같습니다.

DFS트리에다 back edge, forward edge, cross edge를 그려보면 다음과 습니다.

---

Kosaraju's algorithm

강결합 컴포넌트를 분리하는 첫번째 알고리즘입니다. 

위의 그래프 G를 Kosaraju의 알고리즘을 통해 강결합 컴포넌트들로 분리해보면

1. 그래프 G에서 DFS를 하면서 각 정점의 finish time을 저장한다. 

2. 그래프G에서 모든 간선의 방향을 반대로 바꾼 역방향 그래프 T를 만든다.

3. finish time이 큰 정점부터, 즉 늦게 끝난 정점부터 역방향 그래프 T에서 DFS를 한다. 이 때 생기는 DFS트리들이 각각 하나의 SCC이다.

• 1번 정점의 finish time이 가장 크기 때문에, 1번 정점부터 그래프 T에서 DFS를 한다. 4번 정점에서 더이상 갈 곳이 없이 끝나게 된다.

• 아직 방문하지 않은 3, 5, 6번 정점들 중에 5번 정점의 finish time이 가장 크기 때문에, 5번 정점에서 DFS를 시작한다. 6번 정점을 방문하고 끝나게된다.

• 마지막으로 남은 3번 정점에서 DFS를 한다.

DFS트리가 총 3개 생겼고, 각각의 트리가 하나의 SCC가 됩니다.

구현: 

백준 2150번 Strongly Connected Component

#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
int V, E;
vector<int> G[10001];
vector<int> T[10001];
vector<vector<int>> scc;
int cur_time; // finish time 체크를 위한 시간 변수
int ft2vtx[10001]; // ft2vtx[n] = finish time이 n인 정점의 번호
bool visit[10001]; // 방문 체크 배열
void dfs(int here)
{
    visit[here] = true;
    for (int there : G[here])
    {
        if(!visit[there])
            dfs(there);
    }
    ft2vtx[++cur_time] = here;
}
 
// 역방향 dfs
void rdfs(int here, vector<int>& newscc)
{
    newscc.push_back(here);
    visit[here] = true;
    for (int there : T[here])
    {
        if(!visit[there])
            rdfs(there, newscc);
    }
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin >> V >> E;
    for (int i = 0; i < E; ++i)
    {
        int from, to;
        cin >> from >> to;
        G[from].push_back(to);
        T[to].push_back(from);
    }
 
    // dfs
    for (int root = 1; root <= V; ++root) {
        if (!visit[root])
            dfs(root);
    }
 
    // finish time이 큰 정점부터 역방향 dfs
    memset(visit, 0, sizeof(visit));
    for (int time = V; time >= 1; --time) {
        int root = ft2vtx[time];
        if (!visit[root]) {
            vector<int> newscc;
            rdfs(root, newscc);
            sort(newscc.begin(), newscc.end());
            scc.push_back(newscc);
        }
    }
 
    // 출력
    sort(scc.begin(), scc.end());
    cout << scc.size() << "\n";
    for(vector<int>& here : scc) {
        for(int v : here) {
            cout << v << " ";
        }
        cout << "-1\n";
    }
    return 0;
}

---

Kosaraju's algorithm 정당성 증명 

다음 두 가지를 증명하면 이 알고리즘이 정당하다는 것을 보일 수 있습니다.

1. 역방향 그래프에서 DFS를 돌릴 때, 어떠한 정점 v에서 출발하는 DFS는 v와 같은 SCC에 포함되는 모든 정점을 방문한다.

2. 역방향 그래프에서 아직 방문하지 않은 정점들 중, finish time이 가장 큰  v에서 출발하는 DFS는 v와 같은 SCC에 포함되지 않는 점들은 방문하지 않는다.

1번은 자명합니다. 임의의 두 정점 u, v가 그래프G에서 같은 SCC에 속한다면, 그래프 G에서 u → v 경로가 반드시 존재합니다. 그러면 역방향 그래프 T에서 v → u 경로는 반드시 존재하게 됩니다.  따라서 역방향 그래프의 임의의 정점 v에서 출발하는 DFS는 v와 같은 SCC에 속하는 모든 정점을 방문하게 됩니다.

2번을 증명하자면

어떠한 두개의 강결합 컴포넌트 scc1, scc2가 있을 때, 각각의 scc에서  finish time이 가장 큰 점을 각각 v1, v2라 하고, 그 finish time을 f1, f2 (f1 > f2)라고 하자. 그래프 G에서 scc2의 임의의 정점 u에서 scc1의 임의의 정점 v로 오는 간선은 존재할 수 없습니다. 또한 그래프 G에서 scc2 → scc1 간선이 없다면, 역방향 그래프 T에서 scc1 → scc2 간선도 없습니다. 따라서 역방향 그래프에서 v1에서 출발하는 DFS는 scc2에 해당하는 정점들을 방문하지 않습니다. 그렇다면 그래프 G에서 scc2 → scc1 간선이 없다는 것을 증명해봅시다.

scc2에서 scc1으로 오는 간선 b → a 가 있다면

1. 그 간선이 tree edge일 수 있을까요?

그 간선이 tree edge라면 f1 < f2가 될 수밖에 없기 때문에 가정에 모순입니다.

2. 그 간선이 forward edge일 수 있을까요?

그 간선이 forward edge라면 f1 < f2가 될 수밖에 없기 때문에 가정에 모순입니다.

3. 그 간선이 cross edge일 수 있을까요?

그 간선이 cross edge라면 f1 < f2가 될 수밖에 없기 때문에 가정에 모순입니다.

4. 그 간선이 back edge일 수 있을까요?

간선 b → a가 back edge라면, DFS트리에서 a가 b의 조상이고 당연하게도 a → b 경로도 존재한다는 말이 되는데, 그러면 a → b경로도 존재하고 b → a 경로도 존재하게 되므로, 두 정점이 서로 다른 scc에 속한다는 가정에 모순입니다.

방향성 그래프에서 DFS를 할 때, 모든 간선은 저 4가지중 하나에 속하게 되는데, scc2에서 scc1으로 오는 간선 b → a는 4가지중 어느것도 될 수 없으므로 존재할 수 없습니다. 

이로서 Kosaraju's algorithm의 정당성이 증명되었습니다.

---

Tarjan's algorithm 

나중에 추가 예정...