MinhNGUYEN2k4

Kosaraju algorithm || Find strongly connected component

Aug 7th, 2020 (edited)
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int N = 100005;
  5.  
  6. int n,m,tplt=0;
  7. vector<vector<int>> a,b;
  8. stack<int> s;
  9. vector<bool> visited;
  10. vector<int> res[N];
  11.  
  12. void dfs1(int u)
  13. {
  14.     visited[u]=true;
  15.     for(int i = 0; i<a[u].size(); ++i)
  16.     {
  17.         if (!visited[a[u][i]]) {
  18.             dfs1(a[u][i]);
  19.         }
  20.     }
  21.     s.push(u);
  22. }
  23.  
  24. void dfs2(int u, int d)
  25. {
  26.     visited[u]=true;
  27.     for(int i = 0; i<b[u].size(); ++i)
  28.     {
  29.         int v = b[u][i];
  30.         if (!visited[v])
  31.         {
  32.             res[d].push_back(v);
  33.             dfs2(v,d);
  34.         }
  35.     }
  36. }
  37.  
  38. void sol()
  39. {
  40.     for(int i=1; i<=n; ++i) if(!visited[i]) dfs1(i);
  41.     for(int i=1; i<=n; ++i) visited[i]=false;
  42.     while (!s.empty())
  43.     {
  44.         int z = s.top(); s.pop();
  45.         if (!visited[z])
  46.         {
  47.             ++tplt;
  48.             res[tplt].push_back(z);
  49.             dfs2(z,tplt);
  50.         }
  51.     }
  52.     cout << tplt << endl;
  53.     for(int i=1; i<=tplt; ++i)
  54.     {
  55.         cout << res[i].size() << endl;
  56.         for(int v : res[i])
  57.         {
  58.             cout << v << " ";
  59.         }
  60.         cout << endl;
  61.     }
  62. }
  63.  
  64. signed main()
  65. {
  66.     ios_base::sync_with_stdio(false);
  67.     cin.tie(0);cout.tie(0);
  68.     //freopen("sconnect.inp","r",stdin);
  69.     cin >> n >> m;
  70.     a.resize(n+1,vector<int>(0));
  71.     b.resize(n+1,vector<int>(0));
  72.     visited.resize(n+1,false);
  73.     for(int i=1; i<=m; ++i)
  74.     {
  75.         int u,v;
  76.         cin >> u >> v;
  77.         a[u].push_back(v);
  78.         b[v].push_back(u);
  79.     }
  80.     sol();
  81.     return 0;
  82. }
  83.  
Add Comment
Please, Sign In to add comment