[백준] 2150번: Strongly Connected Component (타잔 알고리즘) | C++

 

2150번: Strongly Connected Component

 
 

정답코드

타잔 알고리즘은 크게 세 가지 경우로 나뉜다.
 
1. 아직 방문하지 않은 노드 → 방문한다.
2. 방문했지만 SCC가 아직 아닌 노드 → id값이 더 작은 걸 저장한다.
3. 방문했고 SCC가 형성된 노드 → through 한다.
 
이런 경우를 거치고 현재 노드(id[cur]) id값과 저장된(remember) id 값이 같으면 스택에서 현재 노드를 만날 때까지 pop한다.
 
 
2번, 3번 경우은 아래와 같은 경우이다.
2번 : 노드6의 다음 진로가 노드3인 경우 (노드3 id와 노드6 id 중 더 작은 값을 리턴한다.)
3번 : 노드6의 다음 진로가 노드5인 경우 

 

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#define MAX 10001
#define fse(A,B,C) for(int i=A;i<B;i+=C)
using namespace std;
int V,E, id[MAX],idx=1;
bool already[MAX];
vector<int> g[MAX];
vector<int> stk;
vector<set<int>> answer;
int dfs(int cur){
    stk.push_back(cur);
    int remember=idx;
    id[cur]=idx++;
    
    for(auto next: g[cur]){
        // 아직 방문하지 않은 노드
        if(id[next]==0) remember=min(remember,dfs(next));

        // 방문한 노드지만 scc가 아닌 노드
        if(!already[next]) remember=min(remember, id[next]);
    }

    if(remember==id[cur]){
        set<int> scc;
        while(1){
            int top=stk.back();
            stk.pop_back();
            scc.insert(top);
            id[top]=remember;
            already[top]=true;
            if(top==cur) break;
        }
        answer.push_back(scc);
    }
    return remember;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>V>>E;
    fse(0,E,1){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
    }

    for(int i(1);i<V+1;i++){
        if(id[i]) continue;
        dfs(i);
    }

    cout<<answer.size()<<'\n';
    sort(answer.begin(), answer.end());
    for(auto a:answer){
        for(auto n:a){
            cout<<n<<" ";
        }
        cout<<"-1\n";
    }
}

 

코사라주보다 조금 더 빠르다..!