Offline-Dynamic-Connectivity

説明

辺の追加削除クエリがオフラインで与えられる場合は、Undo可能Union-Findを用いることで効率的に処理できる。

計算量

$O(Q \log Q \log N)$

実装例

Offline-Dynamic-Connectivity($V$, $Q$):= 頂点数 $V$, $Q$ 個のクエリで初期化する。
insert($idx$, $s$, $t$):= 時刻 $idx$ に辺 $s-t$ を追加する。
erase($idx$, $s$, $t$):= 時刻 $idx$ に辺 $s-t$ を削除する。
build():= クエリを全て与えた後に呼び出す。
run($f$):= build() を実行後に呼び出す。各 $i(0 \leq i \lt Q)$ について $f(i)$ が呼び出される。

struct OfflineDynamicConnectivity {
  using edge = pair< int, int >;

  UnionFindUndo uf;
  int V, Q, segsz;
  vector< vector< edge > > seg;
  int comp;

  vector< pair< pair< int, int >, edge > > pend;
  map< edge, int > cnt, appear;

  OfflineDynamicConnectivity(int V, int Q) : uf(V), V(V), Q(Q), comp(V) {
    segsz = 1;
    while(segsz < Q) segsz <<= 1;
    seg.resize(2 * segsz - 1);
  }

  void insert(int idx, int s, int t) {
    auto e = minmax(s, t);
    if(cnt[e]++ == 0) appear[e] = idx;
  }

  void erase(int idx, int s, int t) {
    auto e = minmax(s, t);
    if(--cnt[e] == 0) pend.emplace_back(make_pair(appear[e], idx), e);
  }

  void add(int a, int b, const edge &e, int k, int l, int r) {
    if(r <= a || b <= l) return;
    if(a <= l && r <= b) {
      seg[k].emplace_back(e);
      return;
    }
    add(a, b, e, 2 * k + 1, l, (l + r) >> 1);
    add(a, b, e, 2 * k + 2, (l + r) >> 1, r);
  }

  void add(int a, int b, const edge &e) {
    add(a, b, e, 0, 0, segsz);
  }

  void build() {
    for(auto &p : cnt) {
      if(p.second > 0) pend.emplace_back(make_pair(appear[p.first], Q), p.first);
    }
    for(auto &s : pend) {
      add(s.first.first, s.first.second, s.second);
    }
  }

  int run(const function< void(int) > &f, int k = 0) {
    int add = 0;
    for(auto &e : seg[k]) {
      add += uf.unite(e.first, e.second);
    }
    comp -= add;
    if(k < segsz - 1) {
      run(f, 2 * k + 1);
      run(f, 2 * k + 2);
    } else if(k - (segsz - 1) < Q) {
      int query_index = k - (segsz - 1);
      f(query_index);
    }
    for(auto &e : seg[k]) {
      uf.undo();
    }
    comp += add;
  }
};

検証

Codeforces Dynamic connectivity contest A - Connect and Disconnect

int main() {
  FILE *in, *out;
  in = fopen("connect.in", "r");
  out = fopen("connect.out", "w");

  int N, Q;
  fscanf(in, "%d %d", &N, &Q);
  OfflineDynamicConnectivity odc(N, Q);
  vector< char > T(Q);
  for(int i = 0; i < Q; i++) {
    fscanf(in, " %c", &T[i]);
    if(T[i] == '+' || T[i] == '-') {
      int x, y;
      fscanf(in, "%d %d", &x, &y);
      --x, --y;
      if(T[i] == '+') odc.insert(i, x, y);
      else odc.erase(i, x, y);
    }
  }
  odc.build();
  odc.run([&](int k) {
    if(T[k] == '?') fprintf(out, "%d\n", odc.comp);
  });
}