SCC(Strongly Connected Component)

SCC(Strongly Connected Component)란?

SCC(Strongly Connected Component) 즉, 강한 연결 요소에 대해 알아보고자 한다.

방향 그래프에서 임의의 두 정점 U, V가 있을 때, U->V로 가는 경로가 존재한다면 그 그룹은 SCC이다.

이때 U->V로 가는 경로는 직/간접적인 경로를 의미한다.(U->V로 바로 연결되어있어도 되고, U->...->V로 연결되어있어도 된다.)

SCC(Strongly Connected Component)특징

1. 같은 SCC내에서 뽑은 임의의 U, V 점에서 U->V 혹은 V->U의 경로(직/간접적)는 항상 존재한다.

2. 서로 다른 SCC에서 뽑은 임의의 U, V 점에서 U->V의 직/간접적 경로 혹은 V->U 직/간접적 경로는 존재하지 않는다.

즉, 서로다른 SCC끼리는 사이클이 존재하지 않는다는 의미이다.

3. SCC는 Maximal한 성질을 가지고 있어 SCC가 형성된다면 형성될 수 있는 가장 큰 집합으로 형성이된다.

그림을 통해 SCC 보기

A부터 확인해보자. A와 B는 A->B 혹은 B->A의 경로가 있기에 같은 SCC이다.

A와 D는 A->B->D와 D->C->A가 있기에 같은 SCC이다. C또한 같은 SCC이다.

하지만 H는 A->H만 있지, H->A로 갈 수 있는 경로가 없기에 다른 SCC이다.

E를 보면 A->B->D->E->F->G->E->F->... 즉, A->E는 가능하지만 E->A는 불가능하다.

따라서 다른 SCC이다.

그럼 첫번째 SCC는 A-B-D-C로 묶일 수 있음을 알 수 있다. 이때 SCC의 특성상 Maximal하게 SCC가 구성됨을 확인 할 수 있다.

두번째 SCC는 H 단독으로 SCC를 이루게 되고 세번째 SCC는 E-F-G로 이루어진 SCC를 볼 수 있다.

이 그림을 보면 또 다른 내용을 하나 더 알 수 있게 된다.

결국 초록색 원으로 서로 다른 SCC가 구성되었을 때 사이클이 모두 없어지게 된다는 것을 알 수 있다.

결국 SCC를 구성하게 되면 우리는 사이클이 존재한 방향 그래프에서 또 다른 문제인 위상정렬 문제도 해결 할 수 있는 여건이 마련된다는 것이다.

SCC(Strongly Connected Component) 소스 코드 분석

타잔 알고리즘(Tarjan's Algorithm)

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
 
using namespace std;
 
const int MAX = 10010;
 
// SCCtotal : SCC 개수, sn[i]: i가 속한 SCC의 번호
int V, E, cnt, dfsn[MAX], SCCtotal, sn[MAX];
vector<int> adj[MAX];
bool finished[MAX]; // SCC가 확정된 정점 판별
stack<int> s;
vector<vector<int>> SCC;
 
// SCC에 사용될 dfs
int dfs(int curr)
{
    dfsn[curr] = ++cnt; // dfsn 결정
    s.push(curr); // 스택에 자신을 push
 
    // 자신의 dfsn, 자식들의 결과나 dfsn 중 가장 작은 번호를 result에 저장
    int result = dfsn[curr];
    for (int next : adj[curr])
    {
        // 아직 방문하지 않은 이웃
        if (dfsn[next] == 0)
            result = min(result, dfs(next));
 
        // 방문은 했으나 아직 SCC로 추출되지는 않은 이웃
        else if (!finished[next])
            result = min(result, dfsn[next]);
    }
 
    // 자신, 자신의 자손들이 도달 가능한 제일 높은 정점이 자신일 경우 SCC 추출
    if (result == dfsn[curr])
    {
        vector<int> curSCC;
        // 스택에서 자신이 나올 때까지 pop
        while (1)
        {
            int t = s.top();
            s.pop();
            curSCC.push_back(t);
            finished[t] = true;
            sn[t] = SCCtotal;
 
            if (t == curr)
                break;
        }
 
        // 출력을 위해 원소 정렬
        sort(curSCC.begin(), curSCC.end());
 
        // SCC에 현재 이루어진 SCC 정보 push_back
        SCC.push_back(curSCC);
        SCCtotal++; // SCC 개수 
    }
 
    return result;
}
 
int main() {
    // 그래프 정보 입력
    scanf("%d %d", &V, &E);
    for (int i = 0; i< E; i++) {
        int from, to;
        scanf("%d %d", &from, &to);
        adj[from].push_back(to);
    }
 
    // DFS를 하며 SCC 추출
    for (int i = 1; i <= V; i++)
        if (dfsn[i] == 0)
            dfs(i);
 
    // 출력을 위해 SCC들을 정렬
    sort(SCC.begin(), SCC.end());
 
    // SCC 개수
    printf("%d\n", SCCtotal);
 
    // 각 SCC 출력
    for (auto& currSCC : SCC)
    {
        for (int curr : currSCC)
            printf("%d ", curr);
 
        printf("-1\n");
    }
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

[2150번] Strongly Connected Component :: https://www.acmicpc.net/problem/2150 문제를 이용하여 코드를 설명하고자 한다.

전체적인 코드를 보면 dfsn이라는 개념과 스택과 finished라는 개념, 그리고 result가 가장 핵심이 된다.

dfsn의 의미는 현재 정점에 번호를 매겨주는 역할을 한다.

그리고 스택은 SCC가 구성되기 전까지 계속해서 스택에 쌓여있는 모습을 볼 수 있게 된다.

마지막으로 finished라는 개념은 현재 정점이 SCC를 이루었다면 finished[i] = true가 될 것이다.

마지막으로 result라는 개념은 이제 스택에서 SCC를 구성시키냐 마냐를 결정하는 변수가 된다.

그리고 dfs함수의 리턴은 result를 리턴함으로써 SCC를 구성할 수 있는 요건을 만들어준다.

위의 그림을 보고 코드와 연관지어 생각해보자.

우선 A부터 출발하면 dfsn[A] = 1이 되고 스택에 push될 것이다. (현재 스택 : A)

그다음 result는 1이 되고 A와 연결되어있는 간선 즉 B로 다음 dfs가 넘어가게 된다.

B는 그럼 dfsn[B] = 2가 되고 스택에 push가 된다.(현재 스택 : B A)

그리고 result는 2가 되고  B와 인접한 간선 즉 D로 향하게 된다.

D는 dfsn[D] = 3, 현재 스택 (현재 스택 : D B A), result = 3, C로 향하게 된다.

C에서는 dfsn[C] = 4, 현재 스택 (현재 스택 : C D B A)가 된다.

이때 C에서 뻗어지는 간선이 A쪽뿐인데 if(dfsn[next] == 0)일 경우 dfs를 돌리지, dfsn[A] = 1이기에 결국 else if로 향한다.

A가 아직 finished배열이 이용되지 않았기에 result = min(4, dfsn[A]) 즉 min(4,1)이 되어 result는 1이 된다.

이렇게 계속해서 dfs가 리턴되다가 마지막 A의 dfs로 왔을 때 if(result == dfsn[curr]에 걸리게 되어 결국

현재 스택에 존재한 값 C D B A 가 하나의 SCC를 이루게 된다.

이때 사실 H로의 방문이 있지만, 위와 똑같은 원리로 동작하기에 따로 설명을 하지 않으려 한다.

결과적으로 위와 같이 총 3개의 SCC가 생성된다.

사실 SCC 소스 코드 자체는 무거운 내용이 없기 때문에 충분히 이해 할 수 있을 것이라 생각이 든다.