tarjan求强联通分量

变量含义说明：

pre[i]:i点的被访问的时钟编号，被分配后保持不变

low[i]:i点能访问的最先的点的时钟编号，随子节点改变

scc_no[i]:i点所在的强联通分量的编号

dfs_clock:时钟序号，每访问一个新的点时都增长1

scc_cnt:强联通分量的编号

栈stk:每访问一个节点都压入栈中

他的步骤如下所述：

1. 从根节点开始访问
2. 为此新点的pre和low赋值现在的时间
3. 遍历访问它的子节点
   如果此点未被访问，则跳回第二步，然后跟新其low值
   如果已访问但其未进入强联通编号，则用此点pre更新父节点的low值
4. 遍历完子节点后，如果发现此点的low值和pre值相等，则说明它是所在强联通分量的拥有最小时间访问编号的那个点，于是可以从栈stk中弹出他的后续所有节点，并为他们赋值一个新的强联通分量的编号。

具体代码如下；

@Frosero

#include <iostream>

#include <cstring>

#include <stack>

#include <vector>

int low[202],pre[202],scc_no[202],dfs_clock,scc_cnt;

vector<int>mps[202];

stack<int>stk;

void tarjan(int s){

    pre[s] = low[s] = ++dfs_clock;

    stk.push(s);

    for(int i=0;i<mps[s].size();i++){

        int v = mps[s][i];

        if(!pre[v]){

            tarjan(v);

            low[s] = min(low[s],low[v]);

        }

        else if(!sccno[v]){

            low[s] = min(low[s],pre[v]);

        }

    }

    if(pre[s] == low[s]){

        scc_cnt++;

        while(true){

            int x = stk.top(); stk.pop();

            sccno[x] = scc_cnt;

            if(x == s) break;

        }

    }

}

void fin_circle(int s){

    memset(pre,0,sizeof(pre);

    dfs_clock = scc_cnt = 0;

    tarjan(s);

}