在最近学习中遇到了几次题解使用Tarjan的情况，便查了一些资料。
算法简介
一种由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法。
前置解释
1.如果有向图两个顶点可以相互通达，则称两个顶点强连通(strongly connected)。
2.如果有向图G的每两个顶点都强连通，称G是一个强连通图。
3.有向图的极大强连通子图，称为强连通分量(strongly connected components)。
举个例子
图1
在图1中，图{1,2,3,4}为一个强连通分量，因为1，2，3，4，都可以两两到达，当然｛5｝，｛6｝也是两个强连通分量。
而我们Tarjan算法的目的就是求解有向图的强连通分量
Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
图解模拟有如下定义。
DFN[ i ] : 在DFS中该节点被搜索的次序(时间戳)
LOW[ i ] : 为i或i的子树能够追溯到的最早的栈中节点的次序号
当DFN[ i ]==LOW[ i ]时，为i或i的子树可以构成一个强连通分量。
以1号节点为Tarjan 算法的起始点，以DFS序开始搜
顺次DFS搜到节点6，同时更新DFN,LOW
开始回溯，发现LOW[ 5 ]==DFN[ 5 ] , LOW[ 6 ]==DFN[ 6 ] ,则{ 5 } , { 6 } 为两个强连通分量。
拓展节点1 ， 发现1在栈中更新LOW[ 4 ]，LOW[ 3 ] 的值为1
回溯节点1，拓展节点2
至此，Tarjan Algorithm 结束，{1 , 2 , 3 , 4 } , { 5 } , { 6 } 为图中的三个强连通分量。
时间复杂度
O（E+V）
每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次
参考代码
伪代码
tarjan(u)
{
DFN[u]=Low[u]=++Index//为节点u设定次序编号和Low初值
Stack.push(u)//将节点u压入栈中
for each(u,v) in E//枚举每一条边
if (visnotvisted)//如果节点v未被访问过
tarjan(v)//继续向下找
Low[u]=min(Low[u],Low[v])
else if (vinS)//如果节点v还在栈内
Low[u]=min(Low[u],DFN[v])
if (DFN[u]==Low[u])//如果节点u是强连通分量的根
repeat{
v=S.pop//将v退栈，为该强连通分量中一个顶点
printv
until(u==v)
}
}
C++代码
void tarjan(int x){
dfn[x]=low[x]=++tot;//入栈
sta[++num]=x;insta[x]=true;
for(int i=head[x];i;i=edge[i].next){
if(!dfn[edge[i].to]){
tarjan(edge[i].to);
low[x]=min(low[x],low[edge[i].to]);
}
else if(insta[edge[i].to])
low[x]=min(low[x],dfn[edge[i].to]);
}
if(low[x]==dfn[x]){
sa=0;
do{sa++;insta[sta[num--]]=false;}//弹栈
while(x!=sta[num+1]);
if(sa==2){puts("2");exit(0);}//到2就没必要继续了
if(sa>1)ans=min(ans,sa);//取最小值
}
}
以下列出参考的文章，感谢这些作者提供的文章。
1.Tarjan 算法&模板
2.P2661 信息传递 tarjan
3.百度百科-tarjan算法
