matbensch

SCC Kosaraju C++

Jan 19th, 2023
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.98 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int n;
  8. vector<vector<int>> adj;
  9. vector<vector<int>> adj_t;
  10. vector<bool> vis;
  11. vector<int> comp;
  12. vector<int> order;
  13.  
  14. void visit(int u)
  15. {
  16.     vis[u] = true;
  17.     for(int v:adj[u]) if(!vis[v]) visit(v);
  18.     order.push_back(u);
  19. }
  20.  
  21. void assign(int u, int k)
  22. {
  23.     comp[u] = k;
  24.     for(int v:adj_t[u]) if(comp[v]==-1) assign(v, k);
  25. }
  26.  
  27. void scc()
  28. {
  29.     adj_t.resize(n);
  30.     for(int u=0;u<n;u++) for(int v:adj[u]) adj_t[v].push_back(u);
  31.  
  32.     vis.resize(n);
  33.     for(int u=0;u<n;u++) if(!vis[u]) visit(u);
  34.     reverse(order.begin(), order.end());
  35.  
  36.     comp.assign(n, -1);
  37.     int curr = 0;
  38.     for(int u:order) if(comp[u]==-1) assign(u, curr++);
  39. }
  40.  
  41. int main()
  42. {
  43.     n = 7;
  44.     adj = {
  45.         {5,6},
  46.         {0},
  47.         {1,3,6},
  48.         {4},
  49.         {3},
  50.         {0,4},
  51.         {1,3}
  52.     };
  53.     scc();
  54.     cout << "SCCs: ";
  55.     for(int e:comp) cout << e << ' ';
  56.     cout << '\n';
  57. }
Advertisement
Add Comment
Please, Sign In to add comment