강한 결합 요소 (Strongly Connected Component)

SCC란, 방향 그래프에서 정의되는 개념으로, 한 SCC 내부에서 임의의 정점 u, v를 잡았을 때, u에서 v가 도달 가능한 컴포넌트를 의미한다.

 

한 그래프에는 여러개의 SCC가 존재할 수 있고, 이러한 SCC들을 분리해 내고 그 SCC들을 하나의 정점처럼 합쳐 주면 압축된 새로운 그래프를 얻을 수 있다. 이 그래프는 무조건 DAG 이고, 이를 이용하여 많은 문제들을 풀수 있다. ( 압축된 정점 들 간의 사이클이 존재하면 임의의 한 압축정점에서 다른 정점으로 양방향경로가 존재하니, 그 압축정점들 또한 하나의 SCC로 뭉쳐져야 한다. )

 

SCC는 $O(N+M)$ 안에 추출할 수 있고, Tarjan과 Kosaraju 두 방법이 있다.

 

 

1. Tarjan's Algorithm

타잔의 알고리즘은 기본적으로 그래프를 DFS 스패닝 트리로 만든 후 생각한다.

이렇게 생각하는 이유는 하나의 SCC는 DFS 스패닝 트리에서도 서로 연결되어 있는 정점들이기 때문이다.

(아니라 가정하자. 아니면 그 사이에 정점 w가 끼어 있다는 뜻인데, 부모 u, 자식 v는 한 SCC에 속해야 한다. 하지만 그들이 한 SCC라는 뜻은 v->u->w 가 존재하고 w->v 가 존재하니 모순이다.)

 

 

(이미지 출처 : kks227님 블로그)

 

일단, 첫번째로 트리에서의 순방향 간선은 무시 가능하다. 순방향 간선을 타는 경로가 있으면, 트리 간선들만을 이용해도 똑같은 경로가 존재하기 때문이다.

이제 트리 간선, 역방향 간선, 순방향 간선들만 생각해 보자.

 

타잔 알고리즘을 구현할 때 필요한 것들은 다음과 같다.

vis 배열(정점의 방문 여부) , fin 배열(정점이 SCC로 묶여 있는가 여부) , dis 배열(그 정점의 방문 순서), 스택 S

 

dfs 함수는 그 노드를 루트로 하는 서브트리에서 도달 가능한 가장 방문순서가 빠른 정점을 반환한다.

이를 다음과 같이 수행한다.

 

현재 방문한 정점이 u일때, 

0. 방문할 때 vis 체크, dis 체크 및 스택에 추가해 준다.

1. 인접한 정점들을 모두 돌면서 만약 v가

   1. 방문되지 않은 정점이면, 트리 간선이므로 따라가고, 그 정점에서의 반환값을 받아온다.

   2. 이미 방문된 정점이다. 만약 이 정점이 이미 어떤 SCC에 묶여 있다고 생각해 보자. 이 정점이 SCC에 묶여 있다는 뜻은, u->v가 존재해도, v->u가 존재하지 않는다는 뜻이기 때문에 생각할 필요가 없다. 이제 이 정점이 SCC에 묶여 있지 않다면? 반환값에 v도 고려하여 정점 u에서 SCC가 끝날 수 없게 해주면 된다.

2. 이제 이 섭트리에서 도달 가능한 가장 방문순서가 빠른 정점이 자기 자신인 u라 하자.

이 정점들은 하나의 SCC로 묶어줘야 한다. 따라서 스택에서 자기 자신이 나올때까지 빼주고, 이 정점들을 하나의 SCC로 묶어 주면 된다.

 

역간선과 교차 간선은 모두 그 정점이 자신만의 SCC로 묶이지 못하게 하는 역할을 해준다.

 

또한 잘 생각해 보면, 이 알고리즘은 DFS 를 돌면서 트리의 리프 부분부터 SCC를 묶는다. 이를 다르게 생각해보면, dfs 종료 순으로 묶인다는 것이고, 이는 결국 위상정렬의 역순으로 SCC를 뽑아낸다는 것을 의미한다. 따라서 번호를 매긴 것을 뒤집어 주면, SCC를 구하고, 이를 위상정렬까지 하는 셈이 된다.

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e4;

int n, m;
vector<int> adj[MAXN+10];

vector<int> S;
bool vis[MAXN+10], fin[MAXN+10];
int dis[MAXN+10], cnt=1;
int scc[MAXN+10], scnt=1;
vector<vector<int>> ans;

int dfs(int now)
{
    vis[now]=true; dis[now]=cnt++;
    S.push_back(now);
    int ret=dis[now];

    for(int nxt : adj[now])
    {
        if(!vis[nxt]) ret=min(ret, dfs(nxt));
        else if(!fin[nxt]) ret=min(ret, dis[nxt]);
    }

    if(ret==dis[now])
    {
        vector<int> curscc;
        while(1)
        {
            int t=S.back();
            S.pop_back();
            curscc.push_back(t);
            fin[t]=true;
            scc[t]=scnt;
            if(t==now) break;
        }
        scnt++;
        sort(curscc.begin(), curscc.end());
        ans.push_back(curscc);
    }
    return ret;
}

int main()
{
    int i, j;

    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
    }
    for(i=1; i<=n; i++) if(!vis[i]) dfs(i);

    sort(ans.begin(), ans.end());
    printf("%d\n", ans.size());
    for(i=0; i<ans.size(); i++)
    {
        for(int it : ans[i]) printf("%d ", it);
        printf("-1\n");
    }
}

 

2. Kosaraju's Algorithm

코사라주 알고리즘은 스패닝 트리보다는 위상정렬과 비슷한 아이디어로 SCC를 추출해 낸다.

 

코사라주 알고리즘에서 필요한 것들은 다음과 같다.

adj(인접 리스트), revadj(역그래프의 인접 리스트), S(종료시간의 역순으로 방문할 수 있게 해줄 스택)

 

1. 그래프에서 dfs를 돌리고, 종료시간으로 스택에 기록한다.

2. 스택에서 하나씩 빼며 (==스택을 뒤집고 앞에서부터 하나씩 보며) 종료시간의 역순으로 역그래프에서 dfs2를 돌린다. 이때 한번 dfs2 돌면서 도달 가능한 정점들은 모두 하나의 scc이다.

 

이 알고리즘이 성립하는 느낌과, 증명을 해 보자.

느낌은 다음과 같다. 먼저 위상정렬처럼 종료 역순을 고려한다는 것은 어쨋건 결론 SCC의 압축된 새로운 정점을 기준으로 봤을때 위상정렬했을 때의 가장 앞 정점을 얘기한다는 것이고, 거기서의 임의의 정점 하나를 골라 역그래프에서 도달 가능한 모든 정점들을 생각해보자. 위상정렬상의 제일 앞 정점이므로 그 SCC이외의 다른 SCC로는 가지 못할 것이라는 생각을 할 수 있다. 그러면 이를 묶어주면 하나의 SCC이다.

 

증명은 다음 2가지를 증명하면 된다.

1. 종료 역순으로 본 임의의 정점 v에서는 v의 SCC내부의 모든 점들을 다 갈 수 있다.

2. v의 SCC가 아닌 점들은 아무도 못간다.

1번은 자명하고, 2번은 위상정렬의 정당성 분석과 똑같이, DFS 트리 간선 분류를 통해 구할 수 있다.

 

위상정렬 느낌으로 탐색을 진행하기 때문에, 코사라주는 DAG 에서 앞쪽 물체부터 SCC로 묶기 시작한다.

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e4;

int n, m;
vector<int> adj[MAXN+10];
vector<int> revadj[MAXN+10];

bool vis1[MAXN+10];
vector<int> order;
void dfs1(int now)
{
    vis1[now]=true;
    for(int nxt : adj[now]) if(!vis1[nxt]) dfs1(nxt);
    order.push_back(now);
}

bool vis2[MAXN+10];
int scc[MAXN+10], col=1;
void dfs2(int now)
{
    vis2[now]=true; scc[now]=col;
    for(int nxt : revadj[now]) if(!vis2[nxt]) dfs2(nxt);
}

int main()
{
    int i, j;

    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        revadj[v].push_back(u);
    }

    for(i=1; i<=n; i++) if(!vis1[i]) dfs1(i);
    reverse(order.begin(), order.end());

    for(int it : order) if(!vis2[it]) dfs2(it), col++;

    vector<vector<int>> ans(col);
    for(i=1; i<=n; i++) ans[scc[i]].push_back(i);

    for(i=1; i<ans.size(); i++) sort(ans[i].begin(), ans[i].end());
    sort(ans.begin(), ans.end());
    printf("%d\n", ans.size()-1);
    for(i=1; i<ans.size(); i++)
    {
        for(int it : ans[i]) printf("%d ", it);
        printf("-1\n");
    }
}