NP-Nidzo

Tarjan's Algorithm SCC

Aug 10th, 2020
1,235
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.01 KB | None | 0 0
  1.  
  2. /**------------------------
  3.     Author : NikolaP
  4.     Compiler : C++
  5. -------------------------*/
  6.  
  7. //{         Setup
  8.  
  9.     #include <bits/stdc++.h>
  10.     using namespace std;
  11.  
  12.     typedef long long int ll;
  13.     typedef long double ld;
  14.     typedef vector<int> vi;
  15.  
  16.     const int inf = INT_MAX;
  17.     const bool debug = 0;
  18.  
  19. //}
  20.  
  21. struct tarjan{
  22.     int n,time;
  23.     vector<vi> graph;
  24.  
  25.     tarjan(int _n,int m){
  26.         n = _n;
  27.         time = 0;
  28.         graph.resize(n);
  29.        
  30.         for(int i = 0 ; i<m ; ++i){
  31.             int from, to;
  32.             cin >> from >> to;
  33.             graph[from].push_back(to);
  34.         }
  35.     }
  36.  
  37.     void FindComponent(int idx, vi& disc, vi& low, stack<int>& s, vector<bool>& stackitem){
  38.         disc[idx] = low[idx] = ++time;
  39.        
  40.         s.push(idx);
  41.         stackitem[idx] = true;
  42.  
  43.         for(int i = 0; i < graph[idx].size(); ++i){
  44.             int to = graph[idx][i];
  45.  
  46.             if(disc[to] == -1){
  47.                 FindComponent(to,disc,low,s,stackitem);
  48.                 low[idx] = min(low[idx], low[to]);
  49.             }
  50.  
  51.             else if(stackitem[to]){
  52.                 low[idx] = min(low[idx],disc[to]);
  53.             }
  54.        
  55.         }
  56.  
  57.         if(low[idx] == disc[idx]){
  58.             while(s.top() != idx){
  59.                 int popped = s.top();
  60.  
  61.                 cout << popped<< " ";
  62.                 stackitem[popped] = false;
  63.  
  64.                 s.pop();
  65.             }
  66.  
  67.             cout << s.top() << '\n';
  68.             stackitem[s.top()] = false;
  69.             s.pop();
  70.         }
  71.     }
  72.  
  73.     void SCC(){
  74.         vi disc(n,-1),low(n,-1);
  75.         vector<bool> stackitem(n,false);
  76.         stack<int> s;
  77.  
  78.         for(int i = 0; i < n; ++i){
  79.             if(disc[i] == -1) FindComponent(i,disc,low,s,stackitem);
  80.         }
  81.     }
  82. };
  83.  
  84. int main()
  85. {
  86.     ios::sync_with_stdio(false);
  87.     cin.tie(0);
  88.     cout.precision(8);
  89.     //cout << fixed;
  90.  
  91.     int n,m;
  92.     cin >> n >> m;
  93.  
  94.     tarjan t = tarjan(n,m);
  95.     t.SCC();
  96.  
  97.     return 0;
  98. }
  99.  
  100.  
  101.  
  102.  
Advertisement
Add Comment
Please, Sign In to add comment