图论-求有向图的强连通分量(Kosaraju算法)

求有向图的强连通分量
    Kosaraju算法可以求出有向图中的强连通分量个数,并且对分属于不同强连通分量的点进行标记。
(1) 第一次对图G进行DFS遍历,并在遍历过程中,记录每一个点的退出顺序。以下图为例:
G图
图论-求有向图的强连通分量(Kosaraju算法)
结点第二次被访问即为退出之时,那么我们可以得到结点的退出顺序
  图论-求有向图的强连通分量(Kosaraju算法)
(2)倒转每一条边的方向,构造出一个反图G’。然后按照退出顺序的逆序对反图进行第二次DFS遍历。我们按1、4、2、3、5的逆序第二次DFS遍历:
G`图
 
图论-求有向图的强连通分量(Kosaraju算法)
  
访问过程如下:
  图论-求有向图的强连通分量(Kosaraju算法)
每次遍历得到的那些点即属于同一个强连通分量。1、4属于同一个强连通分量,2、3、5属于另一个强连通分量。
测试数据:
输入:
5 7
1 4
1 5
1 2
2 3
3 5
4 1
5 2
输出:2
 
代码实现:
 #include<iostream>
using namespace std;
#define N 2010
int map[N][N];
int remap[N][N];
int n,m;
int vis[N];
int post[N];
int post_size;
int ans=;
void dfs(int i)
{
vis[i]=;
for(int j=;j<=n;++j)
{
if(map[i][j]&&!vis[j])
dfs(j);
}
post[++post_size]=i;
}
void redfs(int i)
{
vis[i]=;
for(int j=;j<=n;++j)
{
if(vis[j]&&remap[i][j])
redfs(j);
}
}
int main()
{
cin>>n>>m;
for(int i=;i<=m;++i)
{
int x,y;
cin>>x>>y;
map[x][y]=;
remap[y][x]=;
}
for(int i=;i<=n;++i)
{
if(!vis[i])dfs(i);
}
for(int i=n;i>=;--i)
{
if(vis[post[i]])
{
redfs(post[i]);
ans++;
}
}
cout<<ans;
return ;
}
上一篇:关于SVN下载代码和Android Studio里面导入别人代码build tools不一致问题总结


下一篇:ios开发--网页中调用JS与JS注入