[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]
|