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。
因为是从ｕ开始搜到ｖ，所以ｕ的结束时间比ｖ的大。
假设原图中ｕ不指向ｖ，又ｖ的结束时间比ｕ小说明先遍历的ｖ后遍历的ｕ，又原图中 v 可以到达 u，故ｖ的结束时间比ｕ的小。则ｕ的结束时间应该比ｖ的小，与已知矛盾，假设不成立。故原图中ｕ能到达ｖ。
综上，也就是说 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。

代码：

#include <bits/stdc++.h>
using namespace std;
template<typename tp>void in(tp & dig)//读入优化
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,cnt;//cnt 是强连通分量的个数
bool book[10005];
vector<int> g[2][10005];
stack<int> sta;//栈
void initdfs(int u)//初始化 dfs
{
    book[u]=1;
    for(vector<int>::iterator i=g[0][u].begin();i!=g[0][u].end();i++)
        if(!book[*i])initdfs(*i);
    sta.push(u);
}
void dfs(int u)//求强连通分量 dfs
{
    book[u]=1;
    for(vector<int>::iterator i=g[1][u].begin();i!=g[1][u].end();i++)
        if(!book[*i])dfs(*i);
}
int main()
{
    while(in(n),in(m),n|m)//这里必须是 n 或 m——如果边数为 0，点数>0 呢？事实证明是有这种情况的
    {
        for(int i=1;i<=n;i++)g[0][i].clear(),g[1][i].clear();//这里一定要清空
        for(int i=1,a,b;i<=m;i++)
            in(a),in(b),g[0][a].push_back(b),g[1][b].push_back(a);//g[1] 是反向图，g[0] 是原图
        memset(book,0,sizeof(book));
        for(int i=1;i<=n;i++)if(!book[i])initdfs(i);
        memset(book,0,sizeof(book)),cnt=0;//因为两个 dfs 共用了一个 book 数组，所以这里一定要清空
        while(!sta.empty())
        {
            int i=sta.top();sta.pop();
            if(!book[i])cnt++,dfs(i);
        }
        if(cnt>1)printf("No\n");else printf("Yes\n");
    }
    return 0;
}