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

发表评论

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

你是机器人吗? =。= *