SCC 구하기

개요

SCC(강결합 컴포넌트)란 Strongly Connected Component의 약자로, 방향 그래프에서 서로 연결되어 있는 정점들의 집합을 의미합니다. 여기서 말하는 연결은 같은 집합 내 모든 정점들이 서로를 방문할 수 있는 상태를 의미합니다. 영문 위키피디아의 그림을 참고해보면 쉽게 이해할 수 있습니다. 아래 그림을 보면 { a, b, e }는 하나의 집합으로 묶여 있으며, 각각의 정점에서는 같은 집합에 포함된 정점으로 방문할 수 있습니다. 이렇게 방향 그래프을 서브 그래프로 나눈 것을 의미합니다.

출처 : https://en.wikipedia.org/wiki/Strongly_connected_component

 

그럼 SCC는 어디에 사용할 수 있을까요? SCC를 활용하여 그래프를 서브 그래프로 나누면 우리는 SCC를 정점으로 하는 DAG(Directed Acyclic Graph)를 만들 수 있으며, 이 과정을 통해 그래프를 압축할 수 있습니다. 또는 문제 상황을 2-SAT 문제로 치환하여 해결할 수도 있습니다.

 

알고리즘

SCC를 구하는 알고리즘에는 크게 2가지 있습니다. 코사라주 알고리즘과 타잔 알고리즘이 있으며, 시간 복잡도는 동일하기 때문에 편한 알고리즘을 사용하면 됩니다.

 

(1) 코사라주 알고리즘

코사라주 알고리즘은 2번의 DFS 탐색으로 SCC를 찾는 알고리즘입니다. 주어진 그래프와 간선의 방향을 뒤집은 그래프에서 각각 DFS 탐색을 하면서 방문할 수 있는 정점끼리 묶는 알고리즘입니다. 자세한 절차는 다음과 같습니다.

 

(1) 주어진 그래프의 한 정점에서 DFS 탐색을 시작합니다.

(2) 만약 연결된 모든 정점에 방문했다면 현재 정점을 스택에 저장합니다.

(3) 모든 정점이 스택에 저장되면 첫 번째 DFS 탐색이 종료됩니다.

-----------------------------------------------------------------

(4) 이번에는 기존의 그래프에서 간선의 방향을 뒤집은 그래프에서 DFS 탐색을 진행합니다.

(5) DFS 탐색의 순서는 스택에서 정점을 하나씩 pop하면서 진행합니다.

  [1] 만약 현재 정점이 이미 SCC가 정해졌다면( 방문했다면 ) 탐색을 진행하지 않습니다.

  [2] 그렇지 않다면 연결되 정점 중 아직 방문하지 않은 정점들을 DFS 탐색하면서 하나의 SCC로 묶습니다.

 

그래프를 뒤집고, 2번의 DFS 탐색이 필요하지만 개념 및 아이디어가 간단하기 때문에 많이 사용되는 방식입니다. 보통 그래프를 만들 때, 2개의 그래프를 만들어서 알고리즘을 실행합니다. 자세한 소스코드는 다음과 같습니다.

void dfs(int idx) {
    visited[idx] = 1;
    for(int nxt:adj[idx]) {
        if(!visited[nxt]) {
            dfs(nxt);
        }
    }
    
    st.push(idx);
}
 
void Rdfs(int idx) {
    visited[idx] = 1;
    sccNum[idx] = sNum;
    for(int nxt:Radj[idx]) {
        if(!visited[idx]) {
            Rdfs(nxt);
        }
    }
}
 
void sv() {
    for(int i=1;i<=N;i++) {
        if(!visited[i]) dfs(i);
    }
    
    memset(visited, 0, sizeof(visited));
    while(!st.empty()) {
        top = st.top();
        st.pop();
        
        if(!visited[top]) {
            sNum++;
            Rdfs(top);
        }
    }
}

 

(2) 타잔 알고리즘

타잔 알고리즘은 1번의 DFS 탐색으로 SCC를 찾을 수 있습니다. 단절점 알고리즘의 개념을 활용하여 DFS 탐색의 순서와 종료 조건을 기준으로 SCC를 나눌 수 있습니다. 자세한 절차는 다음과 같습니다.

 

(1) 주어진 그래프의 한 정점에서 DFS 탐색을 시작합니다.

(2) 정점에 도달하면 방문 순서를 저장하고, 현재 정점을 스택에 저장합니다.

(3) 현재 방문한 정점과 연결된 정점에 방문하며, 연결된 정점 중 방문 순서가 가장 작은 정점의 번호를 탐색합니다.

  >> 현재 정점과 연결된 모든 정점에서 역간선이 있는지 탐색하는 걸 의미합니다.

(4) 탐색을 끝낸 후, 자신의 방문 순서보다 작은 번호가 나온적이 있는지 확인해봅시다.

  [1] 만약 작은 번호가 나왔다면, 즉 역간선이 있다면 그대로 넘어갑니다.

  [2] 그렇지 않다면, 즉 현재 정점에서 역간선이 없다면 SCC를 구하면 됩니다.

       현재 정점이 나올 때까지 스택에서 정점들을 pop하면서 하나의 SCC로 묶어주면 됩니다.

 

한 번의 DFS 탐색으로 구할 수 있지만, DFS 탐색 순서를 활용하는 알고리즘이라 한 번에 이해하기는 어렵지만 구현하기에는 크게 어려움이 없을 듯 합니다. 자세한 소스코드는 다음과 같습니다.

int getSCC(int idx) {
    int ret;
    
    ret = visited[idx] = ++num;
    st.push(idx);
    
    // 역간선 찾기
    for(int nxt:adj[idx]) {
        if(!visited[nxt]) ret = min( ret, getSCC(nxt) );
        else if(!sccNum[nxt]) ret = min( ret, visited[nxt] );
    }
    
    // 역간선이 없다면 SCC
    if( ret == visited[idx] ) {
        sNum++;
        while(1) {
            top = st.top();
            st.pop();
            
            sccNum[top] = sNum;
            if(top == idx) break;
        }
    }
    
    // 현재 간선에서 가장 높게 올라갈 수 있는 위치 반환
    return ret;
}