Advertisement
MinhNGUYEN2k4

Tarjan algorithm || Find strongly connected component

Aug 8th, 2020 (edited)
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int N = 3*1e5+5;
  5. const int inf = 10000000000005;
  6.  
  7. int n,m,cnt=0,lt=0;
  8. vector<int> a[N];
  9. vector<int> num,low,res[N];
  10. stack<int> st;
  11.  
  12. void dfs(int u)
  13. {
  14.     num[u]=low[u]=++cnt;
  15.     st.push(u);
  16.     for(int v : a[u])
  17.     {
  18.         if (num[v]) low[u] = min(low[u], num[v]);
  19.         else
  20.         {
  21.             dfs(v);
  22.             low[u] = min(low[u],low[v]);
  23.         }
  24.     }
  25.     if (num[u]==low[u])
  26.     {
  27.         ++lt;
  28.         int v;
  29.         do
  30.         {
  31.             v = st.top();
  32.             st.pop();
  33.             res[lt].push_back(v);
  34.             low[v] = num[v] = inf;
  35.         } while (v != u);
  36.     }
  37. }
  38.  
  39. signed main()
  40. {
  41.     ios_base::sync_with_stdio(false);
  42.     cin.tie();cout.tie(0);
  43.     cin >> n >> m;
  44.  
  45.     num.resize(n+1,0);
  46.     low.resize(n+1,0);
  47.  
  48.     while (m--)
  49.     {
  50.         int u,v;
  51.         cin >> u >> v;
  52.         a[u].push_back(v);
  53.     }
  54.     for(int i=1; i<=n; ++i)
  55.     {
  56.         if (!num[i]) dfs(i);
  57.     }
  58.     cout << lt << endl;
  59.     for(int i=1; i<=lt; ++i)
  60.     {
  61.         cout << res[i].size() << endl;
  62.         for(int v : res[i]) cout << v << " ";
  63.         cout << endl;
  64.     }
  65.     return 0;
  66.  
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement