[BOJ 2150] (SCC) Strongly Connected Component

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

SCC문제이다. SCC를 몰라서 이문제 원래는 풀생각이 없었는데 https://www.acmicpc.net/problem/4196 이 문제 단방향인줄 모르고 Union-find 쓰다가 개털려서 공부하고 풀게되었다. 문제는 그냥 SCC를 구현하는 단순한 문제라고 볼수 있다. SCC 관련 포스팅은 추후에 하도록 하겠다. 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
typedef long long ll;
 
using namespace std;
 
int v,e;
vector<vector<int>> vt;
vector<vector<int>> rvt;
vector<vector<int>> scc;
bool visit[11111];
stack<int> st;
 
 
void dfs(int x){
    visit[x] = true;
    
    for(int i=0;i<vt[x].size();i++){
        int next = vt[x][i];
        if(!visit[next]){
            dfs(next);
        }
    }
    st.push(x);
}
 
void func(int x, int c){
    visit[x] = true;
    scc[c].push_back(x);
    
    for(int i=0;i<rvt[x].size();i++){
        int next = rvt[x][i];
        if(!visit[next]){
            func(next,c);
        }
    }
}
 
bool cmp(vector<int > x, vector<int> y){
    return x[0] < y[0];
}
 
int main(){
    
    memset(visit,false,sizeof(visit));
    cin >> v >>e;
    vt.resize(v+1);
    rvt.resize(v+1);
    for(int i=1;i<=e;i++){
        int a,b;
        cin >>a >>b;
        vt[a].push_back(b);
        rvt[b].push_back(a);
    }
    
    for(int i=1;i<=v;i++){
        if(!visit[i]){
            dfs(i);
        }
    }
    
    memset(visit,false,sizeof(visit));
    
    int cnt = 0;
    while(!st.empty()){
        int t = st.top();
        st.pop();
        if(!visit[t]){
            scc.resize(++cnt);
            func(t,cnt-1);
        }
    }
    
    cout << cnt <<endl;
    
    for(int i=0;i<cnt;i++){
        sort(scc[i].begin(),scc[i].end());
    }
    
    sort(scc.begin(),scc.end(),cmp);
    
    for(int i=0;i<cnt;i++){
        for(int j=0;j<scc[i].size();j++){
            cout << scc[i][j]<< " ";
        }cout << "-1\n";
    }
    
    return 0;
}