[백준] 2150번: Strongly Connected Component (코사라주 알고리즘) | C++

 

2150번: Strongly Connected Component

 
 
 

정답코드

이론 공부한 거로 직접 구현해서 최적화된 코드가 아닐 수도 있습니다.
 
1. 정방향 그래프와 역방향 그래프 입력 받기
2. 첫 번째 정방향 DFS 수행
3. 노드 리스트 얻음
4. 두 번째 역방향 DFS 수행
5. SCC 출력
 

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<memory.h>
#define MAX 10001
#define fse(A,B,C) for(int i=A;i<B;i+=C)
using namespace std;
int V,E;
vector<int> g[MAX], rev[MAX];
vector<int> list;
bool visit[MAX];
void dfs(int cur){ // (2)
    if(visit[cur]) return;
    visit[cur]=true;
    for(auto next:g[cur]){
        dfs(next);
    }
    list.push_back(cur); // (3)
}
void dfs2(int cur, set<int> &res){ // (4)
    res.insert(cur);
    visit[cur]=true;
    for(auto next:rev[cur]){
        if(visit[next]) continue;
        res.insert(next);
        dfs2(next,res);
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>V>>E;
    fse(0,E,1){ // (1)
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        rev[b].push_back(a);
    }

    for(int i(1);i<=V;i++){ // (2)
        if(visit[i]) continue;
        dfs(i);
    }

    memset(visit, false, sizeof(bool)*MAX);

    vector<set<int>> answer;
    for(int i(V-1);i>=0;i--){ // (4)
        if(visit[list[i]]) continue;
        set<int> res={list[i]};
        dfs2(list[i], res);
        answer.push_back(res);
    }

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

 
 

코사라주 알고리즘 : 노드 10,000개, 간선 100,000개 일 때 수행 시간 32ms