Advertisement
Oppenheimer

KosaRaju strongly connected components

Jul 12th, 2023
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.31 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define MAX_N 20001
  4. #define ll long long int
  5. using namespace std;
  6. int n, m;
  7.  
  8. struct Node {
  9.   vector < int > adj;
  10.   vector < int > rev_adj;
  11. };
  12.  
  13. Node g[MAX_N];
  14.  
  15. stack < int > S;
  16. bool visited[MAX_N];
  17.  
  18. int component[MAX_N];
  19. vector < int > components[MAX_N];
  20. int numComponents;
  21.  
  22. void dfs_1(int x) {
  23.   visited[x] = true;
  24.   for (int i = 0; i < g[x].adj.size(); i++) {
  25.     if (!visited[g[x].adj[i]]) dfs_1(g[x].adj[i]);
  26.   }
  27.   S.push(x);
  28. }
  29.  
  30. void dfs_2(int x) {
  31.   printf("%d ", x);
  32.   component[x] = numComponents;
  33.   components[numComponents].push_back(x);
  34.   visited[x] = true;
  35.   for (int i = 0; i < g[x].rev_adj.size(); i++) {
  36.     if (!visited[g[x].rev_adj[i]]) dfs_2(g[x].rev_adj[i]);
  37.   }
  38. }
  39.  
  40. void Kosaraju() {
  41.   for (int i = 0; i < n; i++)
  42.     if (!visited[i]) dfs_1(i);
  43.  
  44.   for (int i = 0; i < n; i++)
  45.     visited[i] = false;
  46.  
  47.   while (!S.empty()) {
  48.     int v = S.top();
  49.     S.pop();
  50.     if (!visited[v]) {
  51.       printf("Component %d: ", numComponents);
  52.       dfs_2(v);
  53.       numComponents++;
  54.       printf("\n");
  55.     }
  56.   }
  57. }
  58.  
  59. int main() {
  60.  
  61.   cin >> n >> m;
  62.   int a, b;
  63.   while (m--) {
  64.     cin >> a >> b;
  65.     g[a].adj.push_back(b);
  66.     g[b].rev_adj.push_back(a);
  67.   }
  68.  
  69.   Kosaraju();
  70.   printf("Total number of components: %d\n", numComponents);
  71.  
  72.   return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement