Tarjan算法
Tarjan算法
Tarjan算法是由Robert Tarjan（罗伯特·塔扬）发明的求有向图中强连通分量的算法。
先介绍一下概念
强连通：
如果两个顶点可以相互通达，则称两个顶点强连通。
如果有向图G的每两个顶点都 强连通，称G是一个强连通图。
非强连通图有向图的极大强连通子图，称为强连通分量。
For example：
在这个有向图中1、2、3、4四个点可以互相到达，就称这四个点组成的子图为强连通分量。且这四个点两两强连通。
Tarjan：
dfn[ ]：就是一个时间戳（被搜到的次序），一旦某个点被DFS到后，这个时间戳就不再改变（且每个点只有唯一的时间戳）。所以常根据dfn的值来判断是否需要进行进一步的深搜。
low[ ]：该子树中，且仍在栈中的最小时间戳，像是确立了一个关系，low[ ]相等的点在同一强连通分量中。
注意初始化时 dfn[x] = low[x] = ++cnt.
再考虑从x出发的每条边(x,y)：
对于搜到的点寻找与其有边相连的点，判断这些点是否已经被搜索过，若没有，则进行搜索。若该点已经入栈，说明形成了环，则更新low.
在不断深搜的过程中如果没有路可走了（出边遍历完了），那么就进行回溯，回溯时不断比较low[ ]，取最小的low值。
如果dfn[x]==low[x] 则x可以看作是某一强连通分量子树的根，也说明找到了一个强连通分量，然后对栈进行弹出操作，弹出x和x后面的所有点。
模拟下：
从1进入 dfn［1］＝ low［1］＝ ＋＋cnt = 1
入栈 1
由1进入2 dfn［2］＝low［2］＝ ＋＋cnt = 2
入栈 1 2
之后由2进入4 dfn［4］＝low［4］＝ ＋＋cnt = 3
入栈 1 2 4
之后由4进入 6 dfn［6］＝low［6］＝＋＋cnt = 4
入栈 1 2 4 6
6无出度，之后判断 dfn［6］＝＝low［6］
说明6是个强连通分量的根节点：6及6以后的点出栈并输出。
回溯到4后发现4找到了一个已经在栈中的点1，
更新 low [ 4 ] = min ( low [ 4 ] , dfn [ 1 ] )
于是 low [ 4 ] = 1 .
由4继续回到2
low[2] = min ( low [ 2 ] , low [ 4 ] ).
low［2］＝1；
由2继续回到1 判断 low[1] = min ( low [ 1 ] , low [ 2 ] ).
low［1］还是 1
然后更新3的过程省略
。。。。。。。。。 省略了1->3的更新过程之后，1的所有出边就跑完了
于是判断：low [ 1 ] == dfn [ 1 ] 说明以1为根节点的强连通分量已经找完了。
将栈中1以及1之后进栈的所有点，都出栈并输出。
void tarjan(int now)
{
dfn[now]=low[now]=++cnt; //初始化
stack[++t]=now; //入栈操作
v[now]=1; //v[]代表该点是否已入栈
for(int i=f[now];i!=-1;i=e[i].next) //邻接表存图
if(!dfn[e[i].v]) //判断该点是否被搜索过
{
tarjan(e[i].v);
low[now]=min(low[now],low[e[i].v]); //回溯时更新low[ ]，取最小值
}
else if(v[e[i].v])
low[now]=min(low[now],dfn[e[i].v]); //一旦遇到已入栈的点，就将该点作为连通量的根
//这里用dfn[e[i].v]更新的原因是：这个点可能
//已经在另一个强连通分量中了但暂时尚未出栈，所
//以now不一定能到达low[e[i].v]但一定能到达
//dfn[e[i].v].
if(dfn[now]==low[now])
{
int cur;
do
{
cur=stack[t--];
v[cur]=false; //不要忘记出栈
}while(now!=cur);
}
}关于搜索树
搜索树： 任选一个点进行深度优先遍历，每个点只访问一次，所有发生递归的边构成的树。
有向图的搜索树主要有4 种边（例图只有三种），其中用实线画出来的是树边（tree edge），每次搜索找到一个还没有访问过的结点的时候这就形成了一条树边。
用长虚线画出来的是反祖边（back edge），也被叫做回边。
用短虚线画出来的是横叉边（cross edge），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点并不是当前节点的祖先时形成的 。
除此之外，像从结点1 到结点6 这样的边叫做前向边（forwardedge），它是在搜索的时候遇到子树中的结点的时候形成的。
割点
割点： 在无向连通图（图）中，如果将其中一个点以及所有连接该点的边去掉，图就不再连通，那么这个点就叫做割点
例如，在下图中，0、3是割点，因为将0和3中任意一个去掉之后，图就不再连通。如果去掉0，则图被分成1、2和3、4两个连通分量；如果去掉3，则图被分成0、1、2和4两个连通分量。
注意：
1.割点可能有很多个
2.无向图和有向图都有割点
割边或桥
删去该边后，图会分裂成两个或两个以上不相连的子图。 例如上图0--3和3--4两条边为割边