[BOJ-2150]Strongly Connected Component

강한 연결 요소(Strongly Connected Component)를 구하는 문제이다.

SCC 를 구하기 위해서 사용한 알고리즘은 코사라주 알고리즘을 사용했는데... 이것 말고도 타잔 알고리즘이 사용가능하다고 한다. (아직 안봐서 무엇인지는 모른다....)

방향그래프에서 SCC 를 구하는 것인데 

1. 임의의 어떤 점에서 시작한다. 

2. 정점들의 순서를 구하기 위해서 해당 방향그래프를 순회한다.

3. 정점들의 순서를 구하였다면 순서대로 모든 간선을 정방향에서 -> 역방향으로 돌려 다시 순회하며 SCC를 구한다. 

강한연결요소(SCC ; Strongly Connected Component) : http://wondy1128.tistory.com/110

코사라주 알고리즘(Kosaraju's algorithm) : http://wondy1128.tistory.com/130

#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
#include<utility>
#define din2(a,b) scanf("%d%d", &a,&b)
#define pb(a) push_back(a)
using namespace std;
 
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<pair<int, int> > vpii;
typedef stack<int> si;
const int S = 11111;
vi scc[S]; // Strongly Connected Component
int num_scc; // # of SCC
vb VIS; // vertex visit check
vi DG[S];  // 1: Directed Graph
vi RDG[S]; // 2: Reverse-Directed Graph
si STACK;  // 3: Stack
int V, E;
 
void DG_dfs(int vertex) {
    if (VIS[vertex]) return;
    VIS[vertex] = true;
    for (int i = 0; i < DG[vertex].size(); i++) {
        int here = DG[vertex][i];
        if (VIS[here]) continue;
        DG_dfs(here);
    }
    STACK.push(vertex);
    return;
}
 
void RDG_dfs(int vertex) {
    if (VIS[vertex]) return;
    VIS[vertex] = true;
    for (int i = 0; i < RDG[vertex].size(); i++) {
        int here = RDG[vertex][i];
        if (VIS[here]) continue;
        RDG_dfs(here);
    }
    scc[num_scc].pb(vertex);
    return;
}
 
void make_scc() {
    VIS.clear(); 
    VIS = vb(V + 1, false);
    while (!STACK.empty()) {
        int here = STACK.top(); STACK.pop();
        if (VIS[here]) continue;
        RDG_dfs(here);    
        num_scc++;
    }
    for (int i = 0; i < num_scc; i++) {
        sort(scc[i].begin(), scc[i].end());
    }
    return;
}
 
void kosaraju() {
    for(int vertex = 1 ; vertex <= V ; vertex++) DG_dfs(vertex);
    make_scc();
}
 
void answer() {
    printf("%d\n", num_scc);
    vpii scc_index; // first low-vertex second scc-group index
    for (int group = 0; group < num_scc; group++) {
        scc_index.pb(make_pair(scc[group][0], group));
    }
    sort(scc_index.begin(), scc_index.end() );
    for (int group = 0; group < scc_index.size() ; group++) {
        for (auto p : scc[scc_index[group].second]) {
            printf("%d ",p);
        }
        puts("-1");
    }
}
 
int main() {
    din2(V, E);
    VIS = vb(V+1, false);
    for (int i = 0; i < E; i++) {
        int U, V;
        din2(U, V);
        DG[U].pb(V);
        RDG[V].pb(U);
    } // input 
 
    kosaraju();
    answer();
 
    return 0;
}

#include<cstdio>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
 
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<bool> VB;
typedef stack<int> SI;
 
VVI G;
VVI RG;
VVI ans;
VI vInfoAns;
VB vis;
SI st;
int noV, noE, noAns;
 
void dfs(int vertex){
    for(auto iter = G[vertex].begin() ; iter != G[vertex].end() ; iter++){
        int here = *iter;
 
        if(!vis[here]){
            vis[here] = true;
            dfs(here);
            st.push(here);
        }
 
    }
    return ;
}
 
void dfsReverse(int vertex){
    for(auto iter = RG[vertex].begin() ; iter != RG[vertex].end() ; iter++){
        int here = *iter;
 
        if(!vis[here]){
            vis[here] = true;
            vInfoAns[here] = noAns;
            dfsReverse(here);
            ans[noAns].push_back(here);
        }
    }
    return ;
}
 
int main(){
 
    scanf("%d%d", &noV, &noE);
 
    G = VVI(noV+1, VI(0, 0));
    RG = VVI(noV+1, VI(0, 0));
    ans = VVI(noV+1, VI(0,0));
    vis = VB(noV+1, false);
 
    for(int i = 0 ; i < noE ; i++){
        int u,v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        RG[v].push_back(u);
    } // input data
 
    for(int i = 1 ; i <= noV ; i++){
        if(!vis[i]){
            vis[i] = true;
            dfs(i);
            st.push(i);
        }
    } // vertex sequence 
 
    vis = VB(noV+1, false);
    vInfoAns = VI(noV+1, -1);
    while(!st.empty()){
        int here = st.top(); st.pop();
 
        if(!vis[here]){
            vis[here] = true;
            ans[noAns].push_back(here);
            vInfoAns[here] = noAns;
            dfsReverse(here);
            noAns++;
            sort(ans[noAns-1].begin(), ans[noAns-1].end());
        }
    } // vertex SCC
 
    vis = VB(noAns+1, false);
    printf("%d\n", noAns);
    for(int i = 1 ; i <= noV ; i++){
        int here = vInfoAns[i]; // == noAns
        if(!vis[here]){
            vis[here] = true;
            for(auto iter = ans[here].begin() ; iter != ans[here].end() ; iter++){
                printf("%d ",*iter);
            }
            puts("-1");
        }
    }
 
    return 0;
}