Persistent Union Find
(union-find/persistent-union-find.hpp)

• View this file on GitHub
• Last update: 2026-06-28 15:41:08+09:00
• Include: #include "union-find/persistent-union-find.hpp"

永続 Union Find．

$n$ 頂点 $0$ 辺のグラフに対して連結性を管理し，各状態を snapshot として保存できる． 過去の状態に戻してから更新することで，永続的な Union Find として使える．

• find(v)：頂点 $v$ を含む連結成分の代表頂点を返す．
• size(v)：頂点 $v$ を含む連結成分の頂点数を返す．
• same(u, v)：頂点 $u,v$ が同じ連結成分に含まれるかを返す．
• unite(u, v)：辺 $uv$ を追加する．すでに同じ連結成分なら false，そうでなければ true を返す．
• take_snapshot()：現在の状態を保存し，その番号を返す．
• apply_snapshot(k)：take_snapshot で保存した状態 k に戻す．

永続化には PersistentArray を用いているため，path compression は行わない． union by size により根付き木の高さを抑える．

Depends on

• Persistent Array (data-structure/persistent-array.hpp)

Verified with

• verify/union-find/LC_persistent_unionfind.test.cpp

Code

#pragma once

#include "data-structure/persistent-array.hpp"

struct PersistentUnionFind {
 private:
  PersistentArray<int, 8> a;

 public:
  PersistentUnionFind(int n) { a.build(vector<int>(n, -1)); }
  int find(int x) { return a.get(x) < 0 ? x : find(a.get(x)); }
  int size(int x) { return -a.get(find(x)); }
  bool same(int x, int y) { return find(x) == find(y); }
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (a.get(x) > a.get(y)) swap(x, y);
    *a.mutable_get(x) += a.get(y);
    *a.mutable_get(y) = x;
    return true;
  }
  int take_snapshot() { return a.take_snapshot(); }
  void apply_snapshot(int k) { a.apply_snapshot(k); }
};
/**
 * @brief Persistent Union Find
 * @docs docs/union-find/persistent-union-find.md
 */

#line 2 "union-find/persistent-union-find.hpp"

#line 2 "data-structure/persistent-array.hpp"

template <class T, int B = 8>
struct PersistentArray {
  struct Node {
    T val;
    Node* child[B] = {};
    Node() {}
    Node(const T& v) : val(v) {}
  };
  Node* root;
  vector<Node*> snapshots;
  PersistentArray() : root(nullptr) {}
  T get(Node* t, int k) { return k == 0 ? t->val : get(t->child[k % B], k / B); }
  T get(const int& k) { return get(root, k); }
  pair<Node*, T*> mutable_get(Node* t, int k) {
    t = t ? new Node(*t) : new Node();
    if (k == 0) return {t, &t->val};
    auto p = mutable_get(t->child[k % B], k / B);
    t->child[k % B] = p.first;
    return {t, p.second};
  }
  T* mutable_get(const int& k) {
    auto ret = mutable_get(root, k);
    root = ret.first;
    return ret.second;
  }
  Node* build(Node* t, const T& val, int k) {
    if (!t) t = new Node();
    if (k == 0) {
      t->val = val;
      return t;
    }
    t->child[k % B] = build(t->child[k % B], val, k / B);
    return t;
  }
  void build(const vector<T>& v) {
    root = nullptr;
    for (int i = 0; i < v.size(); i++) root = build(root, v[i], i);
  }
  int take_snapshot() {
    snapshots.push_back(root);
    return snapshots.size() - 1;
  }
  void apply_snapshot(int k) {
    root = snapshots[k];
  }
};

/**
 * @brief Persistent Array
 * @docs docs/val-structure/persistent-array.md
 */
#line 4 "union-find/persistent-union-find.hpp"

struct PersistentUnionFind {
 private:
  PersistentArray<int, 8> a;

 public:
  PersistentUnionFind(int n) { a.build(vector<int>(n, -1)); }
  int find(int x) { return a.get(x) < 0 ? x : find(a.get(x)); }
  int size(int x) { return -a.get(find(x)); }
  bool same(int x, int y) { return find(x) == find(y); }
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (a.get(x) > a.get(y)) swap(x, y);
    *a.mutable_get(x) += a.get(y);
    *a.mutable_get(y) = x;
    return true;
  }
  int take_snapshot() { return a.take_snapshot(); }
  void apply_snapshot(int k) { a.apply_snapshot(k); }
};
/**
 * @brief Persistent Union Find
 * @docs docs/union-find/persistent-union-find.md
 */

Back to top page