本文主要是介绍强连通分量——Kosaraju算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
①随意选取一个结点开始深搜，当搜索完子树时将它压到栈中
②将原图转置（边的方向变成与原来相反），从栈顶节点再进行深搜，每次深搜结束所得的节点就是一个强连通分量
<span style="font-size:14px;">#include<stdio.h>
#include<string.h>
#include<stack>
#include<vector>
#include<iostream>
#include<iomanip>
using namespace std;
vector<int> g[100],gt[100];
bool visit[100];
stack<int> a;
void dfs(int v)
{int i;visit[v]=false;for(i=0;i<g[v].size();i++)if(visit[g[v][i]]) dfs(g[v][i]);a.push(v);
}
void dfs2(int v)
{int i;visit[v]=false;cout<<v<<" ";for(i=0;i<gt[v].size();i++)if(visit[gt[v][i]]) dfs2(gt[v][i]);
}
int main()
{int i,n,m,x,y;cin>>n>>m;for(i=1;i<=n;i++){g[i].clear();gt[i].clear();}while(m--){cin>>x>>y;g[x].push_back(y);gt[y].push_back(x);}memset(visit,true,sizeof(visit));while(!a.empty()) a.pop();for(i=1;i<=n;i++)if(visit[i]) dfs(i);memset(visit,true,sizeof(visit));while(!a.empty()){x=a.top(),a.pop();if(visit[x]){dfs2(x);cout<<endl;cout<<endl;}}
}</span>
这篇关于强连通分量——Kosaraju算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
