4.2.3 Strongly Connected Components (Tarjan)

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
132
133
134

/*

Given a directed graph, determine the strongly connected components (SCCs) using Tarjan's 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. A single depth-first
search keeps visit nodes on a stack and tracks each node's low-link, the smallest entry time
reachable from its subtree; a node whose low-link equals its own entry time roots a component, which
is popped off the stack in one piece.

- `TarjanSCC(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 reverse
  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, SCCs, and component IDs.
- O(n) auxiliary stack space.

*/

#include <algorithm>
#include <climits>
#include <vector>

class TarjanSCC {
  static const int INF = INT_MAX / 2;
  std::vector<std::vector<int>> adj, scc;
  std::vector<int> component, active, lowlink;
  std::vector<char> visit;
  int timer;

  void dfs(int u) {
    lowlink[u] = timer++;
    visit[u] = true;
    active.push_back(u);
    bool is_component_root = true;
    for (int v : adj[u]) {
      if (!visit[v]) {
        dfs(v);
      }
      if (lowlink[u] > lowlink[v]) {
        lowlink[u] = lowlink[v];
        is_component_root = false;
      }
    }
    if (!is_component_root) {
      return;
    }
    std::vector<int> comp_nodes;
    int id = static_cast<int>(scc.size());
    int v;
    do {
      v = active.back();
      active.pop_back();
      lowlink[v] = INF;  // marks v as removed from the active stack
      component[v] = id;
      comp_nodes.push_back(v);
    } while (u != v);
    scc.push_back(comp_nodes);
  }

 public:
  explicit TarjanSCC(int n = 0) : adj(n) {}

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

  void build_scc() {
    int n = static_cast<int>(adj.size());
    scc.clear();
    component.assign(n, -1);
    active.clear();
    lowlink.assign(n, 0);
    visit.assign(n, false);
    timer = 0;
    for (int i = 0; i < n; i++) {
      if (!visit[i]) {
        dfs(i);
      }
    }
  }

  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
  TarjanSCC 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;
}