图的强连通分量-Kosaraju算法

时间:2022-01-14 17:22:06

输入一个有向图,计算每个节点所在强连通分量的编号,输出强连通分量的个数

 #include<iostream>
 #include<cstring>
 #include<vector>
 using namespace std;
 ;
 struct Edge{
     int go,next;
 };
 ,book[maxn];
 vector<int> S;
 vector<int> G[maxn],G2[maxn];
 void dfs(int u)
 {
     vis[u]=;
     ;i<G[u].size();i++){
         int go=G[u][i];
         if(!vis[go]) dfs(go);
     }
     S.push_back(u);
 }
 void dfs2(int u)
 {
     book[u]=count;
     ;i<G2[u].size();i++){
         int go=G2[u][i];
         if(!book[go]) dfs2(go);
     }
 }
 void init()
 {
     memset(vis,,sizeof(vis));
     memset(book,,sizeof(book));
 }
 int main()
 {
     int n,m,a,b;
     scanf("%d %d",&n,&m);
     init();
     ;i<=m;i++)
     {
         scanf("%d %d",&a,&b);
         G[a].push_back(b);
         G2[b].push_back(a);
     }
     ;i<=n;i++) if(!vis[i]) dfs(i);
     ;i>=;i--) if(!book[S[i]]){
         count++;
         dfs2(S[i]);
     }
     cout<<count;
     ;
 }