Kosaraju算法的实现——求强连通分量

admin

[code=Cpp width=700px]#include<cstring>
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
#define M 2012
bool vis[M];                                 //遍历数组
int post[M];                                 //时间戳对应的点
int timestamp;                           //时间戳
int ComponetNumber=0;                //有向图强连通分量个数
vector <int> Edge[M];                //邻接表表示
vector <int> Opp[M];                 //原图的反图
vector <int> Component[M];   //获得强连通分量结果

void dfs(int u)
{                         //第一个dfs确定时间戳
        vis = true;
        for(int i=0;i<Edge.size();i++)
        {
                if(vis[ Edge])        continue;
                //cout<<Edge<<endl;
                dfs(Edge);
        }
        //cout<<"timestamp        "<<timestamp<<"           "<<u<<endl;
        post[timestamp++] = u;
}

void dfs2(int u)
{          //第二个反边dfs确定连通块
        vis = true;
        Component[ComponetNumber].push_back(u);
        for(int i=0;i<Opp.size();i++)
        {
                int v = Opp;
                if(vis[v])  continue;
                dfs2(v);
        }
}

void Kosaraju(int n)
{
        memset(vis,0,sizeof(vis));
        timestamp = 0;
        for(int i=0;i<n;i++)
        {
                if(vis)
                        continue;
                dfs(i);
        }
        memset(vis,0,sizeof(vis));
        ComponetNumber++;
        for(int i=n-1;i>=0;i--)
        {
                //按时间戳从大到小搜
                if(vis[post])        continue;
                Component[ComponetNumber].clear();
                dfs2(post);
                ComponetNumber++;
        }
        ComponetNumber--;          //最后我们把块加了1。。所以要减掉
}
int main()
{
        freopen("a.txt","r",stdin);
        int E,N;
        cin >> N >> E;
        for(int i=1;i<=E;i++)
        {
                int x,y;
                cin >> x >> y;
                Edge[x].push_back(y);
                Opp[y].push_back(x);
        }
        Kosaraju(N);
        cout<<"ComponetNumber is "<<ComponetNumber<<endl;
        for(int i=0;i<N;i++)
        {
                for(int j=0;j<Component.size();j++)
                        cout<<Component[j]<<' ';
                cout<<endl;
        }
        return 0;
}
[/code]

Reserve the liquid. 鈥