SCC (Strong Connected Component) Tarjan解

Strongly Connected Component 


在無向圖當中，只要邊邊相連，即形成連通，不必在意方向。在有向圖當中，由於有了方向限制，因此細分為「強連通」和「弱連通」：所有兩點之間，雙向都有路可通，則是「強連通」；所有兩點之間，至少單向有路可通，則是「弱連通」。

一張有向圖的「強連通分量」，是所有兩點之間，雙向皆有路可通的連通分量。一張有向圖的強連通分量們，不可能互相重疊。

Tarjan解 - DFS紀錄當前節點所連接到最高的祖先，有環則輸出整個環，無環則個別為一個Component

//reference: ACM/ICPC代碼庫  http://ir.hit.edu.cn/~lfwang/docs/MyLib(For%20ACM).pdf
#include<stdio.h>
#include<vector>
#define V 100
#define DBG 0

using namespace std;

vector<int> vec[V];
int id[V], pre[V], low[V], s[V], stop, cnt, scnt;
void tarjan(int v, int n) // vertex: 0 ~ n-1
{
    int t, minc = low[v] = pre[v] = cnt++;
    vector<int>::iterator pv;
    s[stop++] = v;
    for (pv = vec[v].begin(); pv != vec[v].end(); ++pv) {
        if(-1 == pre[*pv]) tarjan(*pv, n);
        if(low[*pv] < minc) minc=low[*pv];
    }
    if(minc < low[v]) {
        low[v] = minc; return;
    }
    do {
        id[t = s[--stop]] = scnt; low[t] = n;
    } while(t != v);
    ++scnt;
}
int main(){
    int a,b,n,m,i;
    memset(pre,-1,sizeof(pre));
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)scanf("%d%d",&a,&b),a--,b--,vec[a].push_back(b);
    for(i=0; i<n; ++i) if(-1==pre[i]) tarjan(i, n);
    printf("scc: %d\n",scnt);
}