啊哈磊_编程从这里起步
标题:
Kosaraju算法的实现——求强连通分量
[打印本页]
作者:
admin
时间:
2013-2-20 20:01
标题:
Kosaraju算法的实现——求强连通分量
[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]
作者:
匿名
时间:
2014-5-28 02:53
Reserve the liquid. 鈥
欢迎光临 啊哈磊_编程从这里起步 (https://bbs.codeaha.com/)
Powered by Discuz! X3.2