Tarjan算法--强连通分量

tarjan的过程就是dfs过程。

图一般能画成树,树的边有三种类型,树枝边 + 横叉边(两点没有父子关系) + 后向边(两点之间有父子关系);

可以看到只有后向边能构成环,即只有第三张图是强连通分量。

对图dfs一下,遍历所有未遍历过的点 ,会得到一个有向树,显然有向树是没有环的。(注意搜过的点不会再搜)

则能产生环的只有指向已经遍历过的点的边,遍历到的点3指向了之前遍历过的点1形成了环。

比如图2的遍历情况:

首先访问3,然后访问1,没有后向边,然后从栈中删除1,继而访问2(入栈),发现2-->1,目前栈中只有{3,2},发现的1并不在栈中,因此2和1没有父子关系,退栈(即2单独是一个强连通分量)。

由于可能出现大环套小环的情况,因而我们需要强化一下dfs过程:

定义:

int Time, DFN[N], Low[N];

DFN[i]表示 遍历到 i 点时是第几次dfs

Low[u] 表示 以u点为父节点的 子树 能连接到 [栈中] 最上端的点 的DFN值(换句话说,是最小的DFN,因为最上端的DFN是最小的嘛)。

例题代码:HDU1269   POJ1236

参考九野博客

 

原文地址:https://www.cnblogs.com/ACMERY/p/4726109.html