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。

代码:

#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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注