Incremental Bridge Connectivity

Code

#include <vector>
#include <tuple>
#include <bitset>
#include <iostream>


struct union_find {
  std::vector<int> par;
  union_find(int N): par(N, -1) {}
  int root(int x) {
    return par[x] < 0 ? x : par[x] = root(par[x]);
  }
  std::tuple<int, int> unite(int x, int y) {
    x = root(x);
    y = root(y);
    if(x == y) return std::make_tuple(x, y);
    if(par[x] > par[y]) std::swap(x, y);
    par[x] += par[y];
    par[y] = x;
    return std::make_tuple(x, y);
  }
  int size(int x) {
    return -par[root(x)];
  }
};


struct incremental_bridge_connectivity {
  static const int MAX_N = 202020;
  static const int MAX_E = 202020;
  std::vector<int> par;
  std::vector<std::pair<int, int>> edge;
  std::bitset<MAX_N> bit;
  std::bitset<MAX_E> bridge;
  union_find cg;
  union_find bcg;

  incremental_bridge_connectivity(int N)
    : par(N, -1), cg(N), bcg(N) {
    }

  int lca(int u, int v) {
    bit = 0;
    while(1) {
      if(u >= 0) {
        if(bit.test(u)) {
          return u;
        }
        bit.set(u);
        if(par[u] < 0) u = -1;
        else u = edge[par[u]].second;
      }
      std::swap(u, v);
    }
  }

  void compress_path(int v, int w) {
    while(v != w) {
      bcg.unite(v, w);
      bridge.reset(par[v]);
      v = edge[par[v]].second;
    }
  }

  void reverse_path(int v, int p) {
    while(true) {
      std::swap(edge[p].first, edge[p].second);
      std::swap(p, par[v]);
      if(p < 0) break;
      v = edge[p].second;
    }
  }

  int add_edge(int u, int v) {
    int ei = edge.size();
    edge.emplace_back(u, v);
    if(bcg.root(u) == bcg.root(v)) {
    }
    else if(cg.root(u) == cg.root(v)) {
      int w = lca(u, v);
      compress_path(u, w);
      compress_path(v, w);
    }
    else {
      bridge.set(ei);
      if(cg.size(u) < cg.size(v)) {
        std::swap(u, v);
        std::swap(edge.back().first, edge.back().second);
      }
      reverse_path(v, ei);
      cg.unite(u, v);
    }
    return ei;
  }

  int size(int v) {
    return bcg.size(v);
  }

  bool is_bridge(int ei) {
    return bridge.test(ei);
  }
};