[백준] 2150: Strongly Connected Component

0. 문제 주소

 

https://www.acmicpc.net/problem/2150

2150번: Strongly Connected Component

 

 

1. 풀이

 

단절점 알고리즘과 매우 유사.

 

dfs ordering을 하면서, 자신과 자신의 자손들이 갈 수 있는 가장 작은 order가 자신이라면,

 

그 점 + 그 점의 자손들은 하나의 SCC를 이룬다.

 

물론 모든 자손은 아니다. 이를 위해 스택을 사용한다.

 

스택에 dfs로 방문하는 순서대로 push 해주고, low (코드에선 ret) 값을 아래와 같이 정의해준다.

 

low = min(curr order, next order, next low)

 

아래 코드에선 order를 dfsn으로, low를 ret로 썼다.

 

주의해야 할 점은 finished 배열이다.

 

next가 이미 방문했던 점이어도 아직 finished되지 않았다면 low 값을 갱신해 주어야 한다.

 

갱신을 완료하고, 만약 이 low 값이 curr의 order값과 같다면 스택에서 SCC를 뽑아내야 한다.

 

 

단절점과 다른 점은, 단절점은 low 값이 order[curr]보다 크거나 같다면 curr가 단절점이라고만 판단하지만,

 

SCC를 뽑아내는 시점을 판단하기 위해선 반드시 low와 order[curr]가 같아야 한다.

 

curr가 나올 때까지 스택에서 pop되는 노드들이 하나의 SCC를 이룬다.

 

여기서 pop을 하며, 그 노드들은 이제는 볼 필요가 없다는 의미로 finished를 true로 만들어 준다.

 

vector를 원소로 갖는 vector로 SCC들을 표현하는 방법이 보편적인 것 같다.

 

 

2. 풀이 코드

 

* 유의할 점

 

 

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

const int MAX = 10005;
using namespace std;

int V, E;
int dfsn[MAX];
bool finished[MAX]; // visit? -> dfsn[i] != 0 
vector<int> graph[MAX];
vector<vector<int>> SCC;
int cnt;
stack<int> st;

int DFS(int curr){
    dfsn[curr] = ++cnt;
    st.push(curr);
    
    int ret = dfsn[curr];
    for (int next: graph[curr]){
        if (dfsn[next] == 0) ret = min(ret, DFS(next));
        else if (!finished[next]) ret = min(ret, dfsn[next]);
    }
    
    if (ret == dfsn[curr]){
        vector<int> currSCC;
        while(true){
            int n = st.top();
            st.pop();
            currSCC.push_back(n);
            finished[n] = true;
            if (n == curr) break;
        }
        
        sort(currSCC.begin(), currSCC.end());
        SCC.push_back(currSCC);
    }
    return ret;
    
} 

int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    scanf("%d %d", &V, &E);
    int u, v;
    for (int i=0;i<E;i++){
        scanf("%d %d", &u, &v);
        graph[u].push_back(v);
    }
    for (int i=1;i<=V;i++){
        if (dfsn[i] == 0) DFS(i);
    }
    
    sort(SCC.begin(), SCC.end());
    
    printf("%d\n", SCC.size());
    for (auto p: SCC){
        for (int curr: p){
            printf("%d ", curr);
        }
        printf("-1\n");
    }

    return 0;
}