백준 2150 strongly connected component

링크

www.acmicpc.net/problem/2150

2150번: Strongly Connected Component

풀이 아이디어

SCC 관련 문제를 처음 풀어보는데 여러 블로그들 글을 참고했다.

자손 9319님 포스팅 jason9319.tistory.com/98 이 가장 깔끔하게 알고리즘을 설명해주신 글 같다.

코사라주 알고리즘을 이용해 문제를 풀었고,

코사라주 알고리즘을 간단히 설명하자면 스택과 역방향 그래프를 만들어 

dfs를 2번 탐색함으로써 SCC를 찾아내는 알고리즘이다. 자세한건 위 블로그 글 참조.

코드

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> vec;
vector<vector<int>> rvec;
vector<vector<int>> scc;
int v,e,r;
stack<int> st;
bool visited[10001];

void dfs(int n){
    visited[n]=true;
    for(int next: vec[n]){
        if(visited[next]) continue;
        dfs(next);
    }
    st.push(n);
}
void dfs2(int n,int i){
    visited[n]=true;
    scc[i].push_back(n);
    for(int next: rvec[n]){
        if(!visited[next])
            dfs2(next,i);
    }
}

int main(void){
    cin>>v>>e;
    vec.resize(v+1);
    rvec.resize(v+1);
    for(int i=0; i<e; i++){
        int x,y;
        cin>>x>>y;
        vec[x].push_back(y);
        rvec[y].push_back(x);
    }
    for(int i=1; i<=v; i++){
        if(!visited[i])
            dfs(i);
    }
    memset(visited, false, sizeof(visited));
    while(st.size()){
        int here = st.top();
        st.pop();
        if(visited[here]) continue;
        scc.resize(++r);
        dfs2(here,r-1);
    }
    for(int i=0; i<r; i++)
        sort(scc[i].begin(),scc[i].end());
    sort(scc.begin(),scc.end());
    cout<<r<<"\n";
    for(int i=0; i<r; i++){
        for(int elem:scc[i])
            cout<<elem<<" ";
        cout<<"-1\n";
    }
}