4.2.2 Strongly Connected Components (Kosaraju)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

/*

Given a directed graph, determine the strongly connected components (SCCs) using the Kosaraju-Sharir
algorithm. A strongly connected component is a maximal set of nodes where every node can reach every
other node. Condensing each SCC into one node produces a directed acyclic graph. The algorithm runs
two passes of depth-first search: the first records the order in which nodes finish, and the second
explores the transposed graph in reverse finish order, with each search collecting exactly one
component.

- `KosarajuSCC(n = 0)` constructs a directed graph of `n` nodes numbered $[0, `n`)$.
- `add_edge(u, v)` adds the directed edge from `u` to `v`.
- `build_scc()` computes the strongly connected components.
- `components()` returns the strongly connected components from the last `build_scc()` call.
- `component_id(v)` returns the component ID containing node `v`. Component IDs are in topological
  order: for every edge from component $a$ to a different component $b$, $a < b$.

Time Complexity:
- O(max(n, m)) per call to `build_scc()`, where $n$ is the number of nodes and $m$ is the number of
  edges.

Space Complexity:
- O(max(n, m)) for storage of the graph, reverse graph, SCCs, and component IDs.
- O(n) auxiliary stack space.

*/

#include <algorithm>
#include <vector>

class KosarajuSCC {
  std::vector<std::vector<int>> adj, rev, scc;
  std::vector<int> component;
  std::vector<char> visit;

  void dfs_order(int u, std::vector<int> &order) {
    visit[u] = true;
    for (int v : adj[u]) {
      if (!visit[v]) {
        dfs_order(v, order);
      }
    }
    order.push_back(u);
  }

  void dfs_component(int u) {
    visit[u] = true;
    component[u] = static_cast<int>(scc.size()) - 1;
    scc.back().push_back(u);
    for (int v : rev[u]) {
      if (!visit[v]) {
        dfs_component(v);
      }
    }
  }

 public:
  explicit KosarajuSCC(int n = 0) : adj(n), rev(n) {}

  void add_edge(int u, int v) {
    adj[u].push_back(v);
    rev[v].push_back(u);
  }

  void build_scc() {
    int n = static_cast<int>(adj.size());
    visit.assign(n, false);
    std::vector<int> order;
    for (int i = 0; i < n; i++) {
      if (!visit[i]) {
        dfs_order(i, order);
      }
    }
    std::reverse(order.begin(), order.end());
    visit.assign(n, false);
    component.assign(n, -1);
    scc.clear();
    for (int u : order) {
      if (!visit[u]) {
        scc.emplace_back();
        dfs_component(u);
      }
    }
  }

  const std::vector<std::vector<int>> &components() const { return scc; }
  int component_id(int v) const { return component[v]; }
};

/*** Example Usage ***/

#include <cassert>
using namespace std;

int main() {
  // 0 ---> 1 ----> 2 <---> 3
  // ^    / |       |       ^
  // |   /  |       |       |
  // |  /   |       |       |
  // | v    v       v       v
  // 4 ---> 5 <---> 6 <---- 7
  KosarajuSCC g(8);
  g.add_edge(0, 1);
  g.add_edge(1, 2);
  g.add_edge(1, 4);
  g.add_edge(1, 5);
  g.add_edge(2, 3);
  g.add_edge(2, 6);
  g.add_edge(3, 2);
  g.add_edge(3, 7);
  g.add_edge(4, 0);
  g.add_edge(4, 5);
  g.add_edge(5, 6);
  g.add_edge(6, 5);
  g.add_edge(7, 3);
  g.add_edge(7, 6);
  g.build_scc();
  // SCC condensation DAG:
  // {0,1,4} -> {2,3,7} -> {5,6}
  //     \-------------------^
  vector<vector<int>> components = g.components();
  for (auto &component : components) {
    sort(component.begin(), component.end());
  }
  sort(components.begin(), components.end());
  assert((components == vector<vector<int>>{{0, 1, 4}, {2, 3, 7}, {5, 6}}));
  assert(g.component_id(0) == g.component_id(1) && g.component_id(1) == g.component_id(4));
  assert(g.component_id(2) == g.component_id(3) && g.component_id(3) == g.component_id(7));
  assert(g.component_id(5) == g.component_id(6));
  assert(g.component_id(0) != g.component_id(2) && g.component_id(2) != g.component_id(5));
  return 0;
}