Hashiryo's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub hashiryo/Library

:heavy_check_mark: Union-Find (undo 可能) (src/DataStructure/UnionFind_Undoable.hpp)

UnionFind_Undoable　クラス

undo可能な Union-Find．
状態が変化しなくても unite を一回呼ぶごとにタイムスタンプが増える．
経路圧縮をしないため計算量は $\log$ になる．

メンバ関数 概要 計算量
UnionFind(n) コンストラクタ. 要素数 $n$ を渡す.  
size(u) 要素 $u$ の属する集合のサイズを返す.  
leader(u) 要素 $u$ の属する集合の代表元を返す. $O(\log n)$
connected(u,v) 要素 $u,v$ が同じ集合に属していれば true を返す． $O(\log n)$
unite(u,v) 要素 $u,v$ それぞれが属する集合を併合する．
すでに要素 $u,v$ が同じ集合に属していれば，false を返す．		 $O(\log n)$
time() この関数を読んだ時点でのタイムスタンプを返す．最初は0． $O(1)$
undo() 直近の unite 操作を無かったことにする． $O(1)$
rollback(t) タイムスタンプ $t$ のときに戻す． 最悪uniteをした回数

Required by

Verified with

Code

#pragma once
#include <vector>
#include <algorithm>
#include <array>
#include <cassert>
class UnionFind_Undoable {
 std::vector<int> par;
 std::vector<std::array<int, 3>> his;
 int cur;
public:
 UnionFind_Undoable(int n): par(n, -1), his{{-1, -1, 1}}, cur(0) { his.reserve(n + 1); }
 int leader(int u) const { return par[u] < 0 ? u : leader(par[u]); }
 bool unite(int u, int v) {
  if (++cur; (u= leader(u)) == (v= leader(v))) return ++his.back()[2], false;
  if (par[u] > par[v]) std::swap(u, v);
  return his.push_back({v, par[v], 1}), par[u]+= par[v], par[v]= u, true;
 }
 bool connected(int u, int v) const { return leader(u) == leader(v); }
 int size(int u) const { return -par[leader(u)]; }
 int time() const { return cur; }
 void undo() {
  if (assert(cur > 0), --cur; --his.back()[2] == 0) {
   auto [v, p, _]= his.back();
   his.pop_back(), par[par[v]]-= p, par[v]= p;
  }
 }
 void rollback(int t) {
  assert(0 <= t), assert(t <= cur);
  if (t == cur) return;
  for (;;) {
   auto &[u, p, i]= his.back();
   if (cur-= i; cur < t) {
    i= t - cur, cur= t;
    break;
   }
   par[par[u]]-= p, par[u]= p, his.pop_back();
  }
 }
};
#line 2 "src/DataStructure/UnionFind_Undoable.hpp"
#include <vector>
#include <algorithm>
#include <array>
#include <cassert>
class UnionFind_Undoable {
 std::vector<int> par;
 std::vector<std::array<int, 3>> his;
 int cur;
public:
 UnionFind_Undoable(int n): par(n, -1), his{{-1, -1, 1}}, cur(0) { his.reserve(n + 1); }
 int leader(int u) const { return par[u] < 0 ? u : leader(par[u]); }
 bool unite(int u, int v) {
  if (++cur; (u= leader(u)) == (v= leader(v))) return ++his.back()[2], false;
  if (par[u] > par[v]) std::swap(u, v);
  return his.push_back({v, par[v], 1}), par[u]+= par[v], par[v]= u, true;
 }
 bool connected(int u, int v) const { return leader(u) == leader(v); }
 int size(int u) const { return -par[leader(u)]; }
 int time() const { return cur; }
 void undo() {
  if (assert(cur > 0), --cur; --his.back()[2] == 0) {
   auto [v, p, _]= his.back();
   his.pop_back(), par[par[v]]-= p, par[v]= p;
  }
 }
 void rollback(int t) {
  assert(0 <= t), assert(t <= cur);
  if (t == cur) return;
  for (;;) {
   auto &[u, p, i]= his.back();
   if (cur-= i; cur < t) {
    i= t - cur, cur= t;
    break;
   }
   par[par[u]]-= p, par[u]= p, his.pop_back();
  }
 }
};
Back to top page