Advertisement
Saleh127

Kosaraju’s Algorithm -Strongly Connected Component

Oct 11th, 2021
1,047
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  5. bool v[200005];
  6. vector<ll>g[200005],g1[200005],topsort;
  7. ll c=0;
  8. void dfs(ll in)
  9. {
  10.      v[in]=1;
  11.  
  12.      for(auto d:g[in])
  13.      {
  14.           if(!v[d])
  15.           {
  16.                dfs(d);
  17.           }
  18.      }
  19.  
  20.      topsort.push_back(in);
  21. }
  22.  
  23. void dfs1(ll in)
  24. {
  25.      v[in]=1;
  26.      //c++;
  27.      for(auto d:g1[in])
  28.      {
  29.           if(!v[d])
  30.           {
  31.                dfs1(d);
  32.           }
  33.      }
  34. }
  35.  
  36.  
  37. int main()
  38. {
  39.    ios_base::sync_with_stdio(0);
  40.    cin.tie(0);cout.tie(0);
  41.  
  42.    ll n,m,i,j,k,l;
  43.  
  44.    cin>>n>>m;
  45.  
  46.    for(i=0;i<m;i++)
  47.    {
  48.         cin>>j>>k;
  49.         g[j].push_back(k);
  50.    }
  51.  
  52.    for(i=1;i<=n;i++)
  53.    {
  54.         if(v[i]==0)
  55.         {
  56.              dfs(i);
  57.         }
  58.    }
  59.  
  60.    memset(v,0,sizeof v);
  61.  
  62.    for(i=1;i<=n;i++)
  63.    {
  64.         for(auto d:g[i])
  65.         {
  66.              g1[d].push_back(i);
  67.         }
  68.    }
  69.  
  70.    for(i=topsort.size()-1;i>=0;i--)
  71.    {
  72.         ll u=topsort[i];
  73.         if(v[u]==0)
  74.         {
  75.              c++;
  76.              dfs1(u);
  77.         }
  78.    }
  79.  
  80.    cout<<"Strongly connected component "<<c<<endl;
  81.  
  82.    return 0;
  83. }
  84.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement