变量含义说明：
pre[i]:i点的被访问的时钟编号，被分配后保持不变 low[i]:i点能访问的最先的点的时钟编号，随子节点改变 scc_no[i]:i点所在的强联通分量的编号 dfs_clock:时钟序号，每访问一个新的点时都增长1 scc_cnt:强联通分量的编号 栈stk:每访问一个节点都压入栈中他的步骤如下所述：
从根节点开始访问为此新点的pre和low赋值现在的时间遍历访问它的子节点 如果此点未被访问，则跳回第二步，然后跟新其low值 如果已访问但其未进入强联通编号，则用此点pre更新父节点的low值遍历完子节点后，如果发现此点的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); }转载于:https://www.cnblogs.com/ScratchingBear/p/5345836.html
