1. 一些没用的东西

在计算机科学中,Kosaraju的算法(也称为Kosaraju-Sharir算法)是线性时间的算法来找到一个有向图的强连通分量。
Aho, Hopcroft 和Ullman相信这个算法是由S. Rao Kosaraju在1978在一个未发表的论文上提出的。
相同的算法还从Micha Sharir 1981年自己出版的书上被单独的发现,这个算法利用了一个事实,即转置图(同图中的每边的方向相反)具有和原图完全一样的强连通分量。——摘自度娘

“为什么有tarjan算法还学这玩意?——因为对于我这个蒟蒻来说tarjan无法理解背不下来= ̄ω ̄=这个算法出奇的简单易懂……”

2. 证明

首先证明一些这句话: 逆图中能根据u搜到的点v,说明原图中v可以到达u,而原图中v一定是u树中的结点,也就是说u可到达v,从而一定能形成强连通分支。
a) 证明:逆图中能根据u搜到的点v,说明原图中v可以到达u。这个很容易证明,因为你在逆图中u能搜到的点v,原图中肯定是v可以到达u。
b) 证明:而原图中v一定是u树中的结点,也就是说u可到达v。
因为是从u开始搜到v,所以u的结束时间比v的大。
假设原图中u不指向v,又v的结束时间比u小说明先遍历的v后遍历的u,又原图中v可以到达u,故v的结束时间比u的小。则u的结束时间应该比v的小,与已知矛盾,假设不成立。故原图中u能到达v。
综上,也就是说u可到达v,从而形成一个强连通分支。但是能把所有的强连通分支都遍历出来吗?根据强连通性的特点,只要u,v为强连通分量,不管逆图还是原图中u和v都能互相到达。结合上面的证明两个节点的推广一下,就证明了能把包含起始节点u的极大强连通分量给遍历出来。

——摘自:poj 2186 korasaju算法 popular cow

3. 实现

我们需要:
1. 一个原图
2. 根据原图建立的反向图(即把所有从i到j的边改成从j到i的边)
3. 一个stack(栈),用于保存初始化dfs得到的倒序
4. book数组,标记是否到达过

程序步骤:
1. 对原图进行初始化dfs,dfs扩展完一个节点后回溯时将当前节点丢到栈中,得到dfs的倒序
2. 从栈中取出栈顶元素,如果该元素未访问过,则在反向图上以该元素为源点进行dfs,dfs所能到达的点都在同一个强连通分量中。
3. 重复步骤2,直到栈空为止。

算法正确性证明见2
具体代码见下

4. 例题&代码

例题:迷宫城堡 HDU - 1269
传送门= ̄ω ̄=
思路:模板题,求强连通分量个数,如果个数>1则输出No,否则输出Yes。

代码: