ACM模版

Tarjan強連通分量

/*
 *  Tarjan 強連通分量
 *  INIT: vec[]為鄰接表; stop, cnt, scnt置0; pre[]置-1;
 *  CALL: for(i=0;i<n;++i)if(-1==pre[i])tarjan(i,n);
 */
const int V = ;

int stop, cnt, scnt;
int id[V], pre[V], low[V], s[V];
vector<int> vec[V];

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 (- == 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;         // 強連通分量的個數
    return ;
}