强连通分量——[Kosaraju算法]
发布时间
阅读量：
阅读量
思路：
[Kosaraju算法]
Kosaraju算法由有向图及其逆图两次深度优先搜索（DFS）构成，在时间复杂度上同样为O(N+M)。该算法的具体步骤如下：
在有向图G中选择一个起始顶点后展开深度优先搜索，在所有邻接节点的探索彻底完成后（即当深度优先搜索函数返回），按照上述顺序将顶点进行排序。
对于有向 图G来说，在其 逆 图G'上执行深度 优先 搜索 。若此次 搜索未能覆盖该 有 向 图的所有 节 点，则应从那些未被覆盖且 最后 完成 搜索 的 节 点中选择重新 开始 。依次 在 逆 图中 进 行 深 度 优 先 搜索 ，直 到 所 有 节 点都被访问 完 成 。
模板：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=1000+10;
int n,m;
vector<int> G[maxn], G2[maxn];//G存原图,G2存逆图
vector<int> S;
int vis[maxn],sccno[maxn],scc_cnt;
void dfs1(int u)
{
if(vis[u]) return ;
vis[u]=1;
for(int i=0;i<G[u].size();i++)
AI写代码 dfs1(G[u][i]);
AI写代码 S.push_back(u); //s[i]表示的是：依次保存最后完成搜索的点
AI写代码
}
void dfs2(int u)
{
if(sccno[u]) return; //还没有搜过
sccno[u]=scc_cnt;
for(int i=0;i<G2[u].size();i++)dfs2(G2[u][i]);
}
void find_scc(int n)
{
scc_cnt=0;
S.clear();
memset(vis,0,sizeof(vis));
memset(sccno,0,sizeof(sccno));
for(int i=0;i<n;i++)dfs1(i);
for(int i=n-1;i>=0;i--)
if(!sccno[S[i]]){scc_cnt++; dfs2(S[i]);}
}
int main()
{
while(scanf("%d%d",&n,&m)==2&&n)
{
for(int i=0;i<n;i++)
{
G[i].clear();
G2[i].clear();
}
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G2[v].push_back(u);
}
find_scc(n);
for(int i=0;i<n;i++)
printf("%d号点属于%d分量\n",i,sccno[i]);
}
}
/*
AI写代码全部评论 (0)
还没有任何评论哟~