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

View this file on GitHub
View document part on GitHub
Last update: 2026-08-04 11:59:54+00:00
Include: #include "structure/union-find/persistent-union-find.hpp"

永続配列を用いた永続 Union-Find です。

PersistentUnionFind オブジェクトをコピーしてから unite することで、併合前の状態を保持したまま新しい状態を作れます。

コンストラクタ

(1) PersistentUnionFind()
(2) PersistentUnionFind(int sz)

(2) は要素数 sz で初期化します。

制約

$0 \leq sz$

計算量

(2) $O(sz)$

find

int find(int k)

要素 k が属する集合の代表元を返します。

制約

$0 \leq k < sz$

計算量

$O(\log sz \cdot \alpha(sz))$

size

int size(int k)

要素 k が属する集合の要素数を返します。

制約

$0 \leq k < sz$

計算量

$O(\log sz \cdot \alpha(sz))$

unite

bool unite(int x, int y)

要素 x と y の属する集合を併合します。
同じ集合なら false、異なる集合を併合したなら true を返します。

制約

$0 \leq x, y < sz$

計算量

$O(\log sz \cdot \alpha(sz))$

Depends on

Persistent Array (structure/others/persistent-array.hpp)

Verified with

Code

#pragma once

#include <vector>

#include "../others/persistent-array.hpp"

/*
 * @brief Persistent-Union-Find(永続Union-Find)
 */
struct PersistentUnionFind {
  PersistentArray<int, 3> data;

  PersistentUnionFind() {}

  PersistentUnionFind(int sz) { data.build(std::vector<int>(sz, -1)); }

  int find(int k) {
    int p = data.get(k);
    return p >= 0 ? find(p) : k;
  }

  int size(int k) { return (-data.get(find(k))); }

  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    auto u = data.get(x);
    auto v = data.get(y);

    if (u < v) {
      auto a = data.mutable_get(x);
      *a += v;
      auto b = data.mutable_get(y);
      *b = x;
    } else {
      auto a = data.mutable_get(y);
      *a += u;
      auto b = data.mutable_get(x);
      *b = y;
    }
    return true;
  }
};

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

#include <vector>

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

#include <utility>
#line 5 "structure/others/persistent-array.hpp"

template <typename T, int LOG>
struct PersistentArray {
  struct Node {
    T data;
    Node* child[1 << LOG] = {};

    Node() {}

    Node(const T& data) : data(data) {}
  };

  Node* root;

  PersistentArray() : root(nullptr) {}

  T get(Node* t, int k) {
    if (k == 0) return t->data;
    return get(t->child[k & ((1 << LOG) - 1)], k >> LOG);
  }

  T get(const int& k) { return get(root, k); }

  std::pair<Node*, T*> mutable_get(Node* t, int k) {
    t = t ? new Node(*t) : new Node();
    if (k == 0) return {t, &t->data};
    auto p = mutable_get(t->child[k & ((1 << LOG) - 1)], k >> LOG);
    t->child[k & ((1 << LOG) - 1)] = 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& data, int k) {
    if (!t) t = new Node();
    if (k == 0) {
      t->data = data;
      return t;
    }
    auto p = build(t->child[k & ((1 << LOG) - 1)], data, k >> LOG);
    t->child[k & ((1 << LOG) - 1)] = p;
    return t;
  }

  void build(const std::vector<T>& v) {
    root = nullptr;
    for (int i = 0; i < (int)v.size(); i++) {
      root = build(root, v[i], i);
    }
  }
};
#line 6 "structure/union-find/persistent-union-find.hpp"

/*
 * @brief Persistent-Union-Find(永続Union-Find)
 */
struct PersistentUnionFind {
  PersistentArray<int, 3> data;

  PersistentUnionFind() {}

  PersistentUnionFind(int sz) { data.build(std::vector<int>(sz, -1)); }

  int find(int k) {
    int p = data.get(k);
    return p >= 0 ? find(p) : k;
  }

  int size(int k) { return (-data.get(find(k))); }

  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    auto u = data.get(x);
    auto v = data.get(y);

    if (u < v) {
      auto a = data.mutable_get(x);
      *a += v;
      auto b = data.mutable_get(y);
      *b = x;
    } else {
      auto a = data.mutable_get(y);
      *a += u;
      auto b = data.mutable_get(x);
      *b = y;
    }
    return true;
  }
};