강한연결요소 : Strongly Connected Component

강한연결요소 : Strongly Connected Component

 

Concept

---

방향 그래프 G의 임의의 노드 쌍 u,v에 대해 u->v, v->u로 가는 경로가 존재하면

G는 Strongly Connected 되었다고 한다

 

따라서 G의 u->v 로 가는 경로가 있을 때, 엣지의 방향을 정반대로 바꾼 transpose G에도 u->v로 가는 경로가 있다면 두 노드 사이에 사이클이 있어 SCC를 만족한다

 

Kosaraju's Algorithm

---

#include <iostream>
#include <vector>
#include <stack>
#include <set>

#define MAX 10001
using namespace std;

int n, out_len;
bool check[MAX], check2[MAX];
vector<int> r[MAX], r2[MAX];
stack<int> S, S2;
set<int> out[MAX];

// for Graph G
void dfs(int x){
    check[x] = true;
    for(auto iter = r[x].begin(); iter != r[x].end(); iter++)
        if (check[*iter] == false)
            dfs(*iter);
    S.push(x); //stack for descending order that DFS's finish time
}
// for transpose Grpah G
void dfs2(int x, int w){
    check2[x] = true;
    for(auto iter = r2[x].begin(); iter != r2[x].end(); iter++)
        if (check2[*iter] == false)
            dfs2(*iter, w);
    out[w].insert(x);
}

int main(void){
    int x, y, m;
    
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        cin >> x >> y;
        r[x].push_back(y); // Graph G
        r2[y].push_back(x); // transpose Graph G^T
    }
    // first dfs to G
    for(int i = 1; i <= n; i++)
        if(check[i] == false)
            dfs(i);
    
    // perform dfs in G^T for G's finish time descending order
    while(!S.empty()){
        int x = S.top();
        S.pop();
        
        if (check2[x]) // if already visited node, pass
            continue;
        
        dfs2(x,++out_len);
    }
    sort(out + 1, out + out_len + 1);
    cout << out_len << '\n'; // the number of SCC groups
    
    for(int i = 1; i <= out_len; i++){
        cout << "GROUP " << i << ": ";
        for(auto iter = out[i].begin(); iter != out[i].end(); iter++)
            cout << *iter << ' ';
        cout << "\n";
    }
    
}