4.2.7 Online Bridge Finding

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

/*

Maintain the number of bridges in an undirected graph while edges are inserted one at a time, along
with the 2-edge-connected components and ordinary connected components. When an inserted edge joins
two different connected components, it creates a new bridge. When it joins two nodes already in the
same connected component, it creates a cycle and every bridge on the path between the two endpoints
stops being a bridge.

- `OnlineBridges(n = 0)` constructs a graph with `n` isolated nodes numbered $[0, `n`)$.
- `add_edge(u, v)` adds the undirected edge `u`-`v` and updates the 2-edge-connected and ordinary
  connected components.
- `bridge_count()` returns the current number of bridges.
- `find_2ecc(u)` returns node `u`'s representative in the 2-edge-connected components partition.
- `find_cc(u)` returns node `u`'s representative in the ordinary connected components partition.

Parallel edges are supported. Adding a second edge between two nodes that are already in the same
connected component dissolves every bridge on the path between them, merging those nodes into the
same 2-edge-connected component.

Time Complexity:
- O(log n) amortized per call to `add_edge()` in this implementation, where $n$ is the number of
  nodes.

Space Complexity:
- O(n) for the disjoint-set arrays and auxiliary parent links.

*/

#include <utility>
#include <vector>

class OnlineBridges {
  std::vector<int> dsu_2ecc, dsu_cc, dsu_cc_size, parent, last_visit;
  int lca_iteration, num_bridges;

  void make_root(int u) {
    u = find_2ecc(u);
    int root = u, child = -1;
    while (u != -1) {
      int p = find_2ecc(parent[u]);
      parent[u] = child;
      dsu_cc[u] = root;
      child = u;
      u = p;
    }
    dsu_cc_size[root] = dsu_cc_size[child];
  }

  void merge_path(int u, int v) {
    lca_iteration++;
    std::vector<int> upath, vpath;
    int lca = -1;
    while (lca == -1) {
      if (u != -1) {
        u = find_2ecc(u);
        upath.push_back(u);
        if (last_visit[u] == lca_iteration) {
          lca = u;
          break;
        }
        last_visit[u] = lca_iteration;
        u = parent[u];
      }
      if (v != -1) {
        v = find_2ecc(v);
        vpath.push_back(v);
        if (last_visit[v] == lca_iteration) {
          lca = v;
          break;
        }
        last_visit[v] = lca_iteration;
        v = parent[v];
      }
    }
    for (int a : upath) {
      dsu_2ecc[a] = lca;
      if (a == lca) {
        break;
      }
      num_bridges--;
    }
    for (int b : vpath) {
      dsu_2ecc[b] = lca;
      if (b == lca) {
        break;
      }
      num_bridges--;
    }
  }

 public:
  explicit OnlineBridges(int n = 0)
      : dsu_2ecc(n),
        dsu_cc(n),
        dsu_cc_size(n, 1),
        parent(n, -1),
        last_visit(n, 0),
        lca_iteration(0),
        num_bridges(0) {
    for (int i = 0; i < n; i++) {
      dsu_2ecc[i] = dsu_cc[i] = i;
    }
  }

  int find_2ecc(int u) {
    if (u == -1) {
      return -1;
    }
    return dsu_2ecc[u] == u ? u : dsu_2ecc[u] = find_2ecc(dsu_2ecc[u]);
  }

  int find_cc(int u) {
    u = find_2ecc(u);
    return dsu_cc[u] == u ? u : dsu_cc[u] = find_cc(dsu_cc[u]);
  }

  void add_edge(int u, int v) {
    u = find_2ecc(u);
    v = find_2ecc(v);
    if (u == v) {
      return;
    }
    int cu = find_cc(u), cv = find_cc(v);
    if (cu != cv) {
      num_bridges++;
      if (dsu_cc_size[cu] > dsu_cc_size[cv]) {
        std::swap(u, v);
        std::swap(cu, cv);
      }
      make_root(u);
      parent[u] = v;
      dsu_cc[u] = v;
      dsu_cc_size[cv] += dsu_cc_size[u];
    } else {
      merge_path(u, v);
    }
  }

  int bridge_count() const { return num_bridges; }
};

/*** Example Usage ***/

#include <cassert>

int main() {
  // 0---1
  //   \ |
  //     2---3
  OnlineBridges g(4);
  g.add_edge(0, 1);
  assert(g.bridge_count() == 1);
  g.add_edge(1, 2);
  assert(g.bridge_count() == 2);
  g.add_edge(2, 0);
  assert(g.bridge_count() == 0);
  g.add_edge(2, 3);
  assert(g.bridge_count() == 1);
  return 0;
}