【模板】强连通分量的kosaraju算法实现
发布时间
阅读量：
阅读量
- 算法思想
Kosaraju算法通过两次深度优先搜索（Dfs）确定有向图中的强连通分量。
在第一次深度优先搜索中，每个节点被访问并按回溯顺序标记编号。完成所有标记后发现，距离搜索树尾部越近的节点获得较小编号。
这相当于对原图中所有强连通分量进行缩点处理后得到的有向无环图（DAG）进行一次拓扑排序。
随后执行第二次深度优先搜索（反向Dfs）。这一次是从具有较大编号的节点开始，在反转后的图中继续探索。
算法正确性的证明参考《挑战程序设计竞赛》第321页相关内容。
-
例题： POJ2186
- 题目大意
给定N头牛以及M组关系(A,B)，其中A表示喜欢B；由于"喜欢"关系具有传递性，请问被全部N头牛所喜爱的有几头这样的牛？
* 分析在每一个强连通分量内部，在这些牛之间必然存在相互喜欢的关系。因此，我们的解决办法是首先识别出所有这些强连通分量然后进行缩点处理。
在缩点的过程中,若存在一个目标节点能够被所有其他目标节点所到达,则该目标必定是一个具有零出度的叶子节点;否则,若该目标具有非零出度则必然会导致图中出现循环结构,而根据题设条件可知这种情况不可能发生.因此,满足上述条件的目标只能存在唯一一个
* 代码 #include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
const int MAXN=10005;
const int MAXM=50005;
int n,m;
bool used[MAXN];
int belong[MAXN];//所属强连通分量的拓扑序，belong[i]表示i属于哪个分支
int out[MAXN];
struct Edge
{
int v;
int next;
}edge[MAXM*2];
int edgecount;
int head[MAXN];
int rhead[MAXN];
void Init()
{
edgecount=0;
memset(head,-1,sizeof(head));
memset(rhead,-1,sizeof(rhead));
}
void Add_edge1(int u,int v)
{
edge[++edgecount].v=v;
edge[edgecount].next=head[u];
head[u]=edgecount;
}
void Add_edge2(int u,int v)
{
edge[++edgecount].v=v;
edge[edgecount].next=rhead[u];
rhead[u]=edgecount;
}
stack<int>Q;
void Dfs(int u)
{
used[u]=1;
for(int k=head[u];k!=-1;k=edge[k].next)
{
int v=edge[k].v;
if(!used[v])Dfs(v);
}
Q.push(u);
}
void rDfs(int u,int group)
{
used[u]=1;
belong[u]=group;
for(int k=rhead[u];k!=-1;k=edge[k].next)
{
int v=edge[k].v;
if(!used[v])rDfs(v,group);
}
}
int scc()//返回强连通分量个数
{
int ans=0;
memset(used,0,sizeof(used));
while(!Q.empty())Q.pop();
for(int i=1;i<=n;i++)
{
if(!used[i])Dfs(i);
}
memset(used,0,sizeof(used));
while(!Q.empty())
{
int x=Q.top();
Q.pop();
if(!used[x]){ans++;rDfs(x,ans);}
}
return ans;
}
int main()
{
int a,b;
Init();
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(out,0,sizeof(out));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
Add_edge1(a,b);
Add_edge2(b,a);
}
int scc_cnt=scc();
for(int u=1;u<=n;u++)
{
for(int k=head[u];k!=-1;k=edge[k].next)
{
int v=edge[k].v;
if(belong[u]!=belong[v])out[belong[u]]++;
}
}
int sum=0;//统计出度为0的点的块数
int x;//出度为0的连通分量编号
for(int i=1;i<=scc_cnt;i++)
{
if(out[i]==0){sum++;x=i;}
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(belong[i]==x)ans++;
}
if(sum==1)cout<<ans<<endl;
else cout<<0<<endl;
}
return 0;
}全部评论 (0)
还没有任何评论哟~