虽然搬家了,但新家还是有点问题,写了这么半天的东西,先发到这里来吧。
其实以前求强连通分支都是用两次深搜,没有实现过Tarjan算法,其实写起来都差不多了。只是细节上容易出现错误。在以下的代码中我把容易错的地方都标注了出来,方便以后查看。。
先贴个两次深搜的代码:
其中第一次是在原图上进行深搜,第二次是在反向图中按照第一次深搜结束时间递减的顺序搜索。这样可以保证第二次搜索的时候每次找到一个强连通分支。
TWICE_DFS

下面介绍一下Tarjan算法: Tarjan算法可以求无向图的块,割点,桥,也可以求有向图的强连通分支,实现的细节不大一样,但思想是一样的,都是利用了搜索树的性质,可以利用子节点的信息来更新父节点求得我们需要的信息。
 low[i]代表由i节点可以达到的编号最小的结点,dfn[i]表示访问的编号,对于无向图,由于在无向图的搜索中不会出现交叉边,所以对节点i的子树进行搜索后,假设i的儿子是j,则如果low[j]>dfn[i],则(i,j)为桥,如果i不是根节点,且low[j]>=dfn[i]或者i是根节点,且儿子数>1,则i为割点。
 在有向图中由于会出现交叉边,所以我们不能像在求无向图的连通分支那样去在有向图中进行搜索。怎样保证求得强连通分支呢,我们可以用一个栈来保存连通分支中的结点,当确定一个连通分支之后退栈。
怎么求得连接两个强连通分支的边呢?low[j]>dfn[i]?这样做是错误的,少考虑了一种情况。如果(i,j)是交叉边,即在搜索i之前j已经搜索过,且j不是i的父节点,则(i,j)也为连接两个强连通分支的边。
(写的我很没有信心,不知道上面的文字对不对,如有错误请各位指正)
代码如下:
Tarjan

 PS:大家可以去看看CmYkRgB123的讲解,很详细。 比我讲的好。。。