强连通分量 Kosaraju科萨拉朱算法

#.图G：图的所有正向边

#. 图rG：图的所有反向边

1. 在G上dfs,标记访问点的先后顺序，，，，递归最底层的点标记最小

2.在rG上dfs,顺序从最大的点到最小的点

#include<iostream>#include<vector>using namesapce std;const int NUM = 1e5+5;vector<int> G[NUM],rG[NUM];int vis[NUM], scnno[NUM];vector<int> S;int cnt; //强连通分量的个数void dfs1(int u){//dfs 正向图if(vis[u]) return ; // 已经访问过vis[u] = 1;for( int i = 0; i < G[u].size(); i++) dfs1(G[u][i]); S.push_back(u);//深的点标记小}void dfs2(int u){//dfs 反向if(scnno[u]) return ; //已经访问过scnno[u] =1;for(int i = 0; i < rG[u].size(); i++) dfs2(rG[u][i]);}void Kosaraju(int n){S.clear();for(int i = 1; i <=n; i++) dfs1(i);for(int j = n-1; j >= 0;j--) if(!scnno[S[i]]) {cnt++;dfs2(S[i]);} //从标记点最大的点开始，}int main(){int n, m, u, v;while(scanf("%d%d",&n, &m),n != 0 || m != 0){for(int i = 0; i < n; i++) G[i] = rG[i] = 0; //n个点for(int i = 0; i < m; i++){//m条边scanf("%d%d", &u, &v);G[u].push_back(v);//正向rG[v].push_back(u); //反向}Kosaraju(n);printf("%d\n",,cnt);}}

如果觉得《强连通分量 Kosaraju科萨拉朱算法》对你有帮助，请点赞、收藏，并留下你的观点哦！