[백준 2150] Strongly Connected Component

 

 그래프 이론 중 SCC 문제. 전에 2-SAT 문제를 풀기 위해 익혔던 SCC 알고리즘을 연습해 보기 위해 따로 고른 문제다. SCC를 찾는 대표적인 알고리즘 중 하나인 코사라주 알고리즘을 어제 구현해 보았고, 타잔 알고리즘도 직접 구현해보고 싶어서 오늘 푼 문제에서는 타잔 알고리즘을 사용했다.

 타잔 알고리즘은 코사라주 알고리즘보다는 비교적 구현이 복잡하지만, DFS를 한 번만 사용해도 된다는 장점이 있다. 큰 맥락은 DFS를 통해 자식을 탐색하다가 어떤 자식이 앞서 탐색한 선조 노드를 방문하는 순간, 이는 사이클이며 그 안의 어떤 노드 두 개를 설정하더라도 서로에게 도달할 수 있다는 의미가 된다. 이는 SCC의 정의에 부합하며, 이 원리를 이용해서 타잔 알고리즘을 구현한다.

 

 저 방식으로 알고리즘을 구현하기 위해서는 방문한 노드가 SCC 형성에 이용된 노드인지 확인할 수 있어야 하고, 각 SCC에 대해 부모 노드라는 개념을 사용해야 한다. 부모 노드는 SCC 내에서 가장 먼저 탐색된 대표 노드라고 생각할 수 있다.

 인접 행렬을 사용하면 비효율 적인 상황이기에 인접 리스트를 사용할 것이고, 입력에서 각 간선 정보가 정렬된 상태로 주어지는 것이 아니기 때문에 나중에 정렬된 상태로 SCC들을 출력해야 한다는 조건을 생각하면서 알고리즘을 작성했다.

 

 나는 isFinished 배열에 각 노드가 SCC 형성이 이미 끝났는지 여부를 저장했고, parentNum 배열에 부모 노드 값을 저장했다. 그리고 SCC 조건을 발견해서 되돌아갈 때, 여태 탐색한 순서의 역순으로 노드를 조회할 수 있어야 하므로 스택 st에 방문하는 노드들을 순서대로 저장해 이용했다.

 

 그다음엔 재귀를 활용하기 위해 dfs 함수를 작성했다. 실제 노드의 번호와 관계없이, 방문하는 순서대로 고유의 번호를 부여하기 위해서 전역변수를 선언해 dfs에 진입할 때마다 증가시켰다. 그리고 방문한 노드의 부모 노드 번호는 일단 본인으로 지정한다. 방문했으므로, 스택 st에 넣어준다.

 

 이후엔 dfs 탐색을 하는데, 먼저 방문 여부부터 확인한다. 해당 노드의 parentNum 값이 0이라면 아직 방문하지 않은 상태이므로, dfs를 계속해서 진행한다. 만약 인접 노드에 대해 dfs를 돌렸는데 받아온 부모 노드 값이 현재 노드 값보다 작다면, 자식 노드를 통해 더 이전에 방문한 노드에 접근 가능하다는 소리이다. 그렇기 때문에 parent 값을 min 값으로 경신한다.

 그리고 방문한 노드라면, SCC처리가 완료된 노드인지 확인한다. 이미 탐색을 통해 다른 SCC에 속한 것이 확인된 노드라면 탐색할 필요 없고, SCC 처리가 완료되지 않은 노드라면 현재 진행 중인 dfs 과정 속에서 이미 방문한 노드라는 뜻이다. 따라서 부모 노드 값을 경신해 준다.

 

 모든 자식 노드를 확인했을 때도, 여전히 부모 노드 값이 나 자신이라면, 현재 노드가 한 SCC의 부모 노드라는 뜻이 된다. 따라서 st에 있던 여태 방문했던 노드들을 역순으로 빼내어 한 SCC로 묶어준다. 이때, 종료 조건은 당연히 스택에서 자신을 빼내는 시점이다.

 그리고 모든 자식 노드를 확인했을 때, 부모 노드 값이 달라졌다면(더 작아질 수밖에 없다) 이는 해당 노드를 포함하는 SCC의 부모 노드가 더 상위 노드라는 뜻이며 그 값은 리턴되어서 재귀에 반영될 것이다.

 

 이 과정을 모든 미방문 노드에 대해 반복하고, 묶어둔 SCC를 문제의 조건에 맞게 출력하면 끝이다. 나는 되도록이면 정렬이나 자료구조를 이용해서 부가적인 시간을 사용하지 않고 선형 탐색으로 끝내고 싶어서, dfs를 통해 각 노드가 속한 SCC 집합의 임의의 번호를 저장해 뒀다가, 이를 1번 노드부터 차례대로 검사하면서 출력을 위한 인덱스로 재배열 하는 방법을 사용했다.

 

 공부한 직후에 작성해서 생각보다 어려움 없이 작성하긴 했는데, 실수하기 좋은 부분이 많은 것 같아서 나중에 관련 문제를 몇 번 더 풀어봐야 할 것 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

int v, e, id = 0, sccInd = 0;
vector<vector<int> > adjList;
vector<bool> isFinished;
vector<int> parentNum;
stack<int> st;
vector<int> sccNums;

int dfs(int x) {
    parentNum[x] = ++id;
    st.push(x);
    
    int parent = parentNum[x];
    for(int adj: adjList[x]) {
        if(parentNum[adj] == 0) { // 방문 이력 x
            parent = min(parent, dfs(adj));
        } else if(!isFinished[adj]) { // 방문 o, scc 처리 x
            parent = min(parent, parentNum[adj]);
        }
    }

    if(parent == parentNum[x]) {
        sccInd++;
        while(true) {
            int cur = st.top();
            st.pop();

            sccNums[cur] = sccInd;
            isFinished[cur] = true;
            if(cur == x) break;
        }
    }

    return parent;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int a, b;
    cin >> v >> e;
    
    adjList = vector<vector<int> >(v+1);
    for(int i=0; i<e; i++) {
        cin >> a >> b;
        adjList[a].push_back(b);
    }

    parentNum = vector<int>(v+1, 0);
    isFinished = vector<bool>(v+1, false);
    sccNums = vector<int>(v+1, 0);

    for(int i=1; i<=v; i++) {
        if(parentNum[i]==0) {
            dfs(i);
        }
    }

    vector<int> sccNumToInd(sccInd+1, 0);
    vector<vector<int> > result(1);

    for(int i=1; i<=v; i++) {
        int ind = sccNumToInd[sccNums[i]];
        if(ind==0) {
            ind = sccNumToInd[sccNums[i]] = result.size();
            result.push_back(vector<int>());
        }
        result[ind].push_back(i);
    }

    cout << sccInd << "\n";

    for(int i=1; i<=sccInd; i++) {
        for(int num: result[i]) {
            cout << num << " ";
        }
        cout << "-1\n";
    }
}