fork download
copy 
  1. /*
  2.   Copyright 2011,2015 Marek "p2004a" Rusinowski
  3.   Computing strongly connected component, Kosaraju's algorithm
  4. */
  5. #include <cstdio>
  6. #include <vector>
  7. #include <algorithm>
  8.  
  9. #define MAXN 1000000
  10.  
  11. std::vector<int> edges[MAXN];
  12. std::vector<int> edges_t[MAXN];
  13. int postorder[MAXN];
  14. bool visited[MAXN];
  15.  
  16. void compute_postorder(int v, int &num) {
  17.   visited[v] = true;
  18.   for (int u: edges[v]) {
  19.     if (!visited[u]) {
  20.       compute_postorder(u, num);
  21.     }
  22.   }
  23.   postorder[num++] = v;
  24. }
  25.  
  26. void compute_scc(int v) {
  27.   visited[v] = true;
  28.   printf("%d ", v + 1);
  29.   for (int u: edges_t[v]) {
  30.     if (!visited[u]) {
  31.       compute_scc(u);
  32.     } 
  33.   }
  34. }
  35.  
  36. int main() {
  37.   int n, m, a, b;
  38.   scanf("%d %d", &n, &m);
  39.   for (int i = 0; i < m; ++i) {
  40.     scanf("%d %d", &a, &b);
  41.     edges[--a].push_back(--b);
  42.     edges_t[b].push_back(a);
  43.   }
  44.   int num = 0;
  45.   for (int i = 0; i < n; ++i) {
  46.     if (!visited[i]) {
  47.       compute_postorder(i, num);
  48.     }
  49.   }
  50.   std::fill(visited, visited + n, false);
  51.   num = 0;
  52.   for (int i = n - 1; i >= 0; --i) {
  53.     if (!visited[postorder[i]]) {
  54.       printf("%d: ", ++num);
  55.       compute_scc(postorder[i]);
  56.       printf("\n");
  57.     }
  58.   }
  59.   return 0;
  60. }
Success #stdin #stdout 0.02s 31736KB
comments (?)
stdin
copy 
8 10
1 2
2 1
2 3
3 4
4 3
2 5
5 6
6 7
7 5
7 8
stdout
copy 
1: 1 2 
2: 5 7 6 
3: 8 
4: 3 4
https://ideone.com/qr3OPA
Kosaraju
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!