首先是求强连通分量：
这个的思路大致就是每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。
代码如下(伪)：
1 void tarjan(int x) 2 { 3 dfn[x]=low[x]=++cnt; 4 instack[x]=1; 5 s.push(x); 6 int y; 7 for(int i=head[x];i;i=e[i].nxt) 8 { 9 y=e[i].to; 10 if(!dfn[y]) 11 { 12 tarjan(y); 13 low[x]=min(low[x],low[y]); 14 } 15 else if(instack[y]) low[x]=min(low[x],dfn[y]); 16 } 17 y=0; 18 if(dfn[x]==low[x]) 19 { 20 tot++; 21 while(x!=y) 22 { 23 y=s.top(); 24 s.pop(); 25 instack[y]=0; 26 belong[y]=tot; 27 } 28 } 29 } 30 void solve() 31 { 32 tot=cnt=0; 33 memset(dfn,0,sizeof(dfn)); 34 For(i,1,n) 35 if(!dfn[i]) tarjan(i); 36 }
原文：https://www.cnblogs.com/3soon/p/11805210.html
