Partially Persistent Union Find (structure/union-find/partially-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/partially-persistent-union-find.hpp"

時刻付きで併合履歴を保持する Union-Find です。

各時刻 t における連結成分の代表元やサイズを問い合わせできます。

コンストラクタ

(1) PartiallyPersistentUnionFind()
(2) PartiallyPersistentUnionFind(int sz)

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

制約

$0 \leq sz$

計算量

(2) $O(sz)$

unite

bool unite(int t, int x, int y)

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

制約

unite を呼ぶ時刻 t は単調非減少
$0 \leq x, y < sz$

計算量

amortized $O(\alpha(sz))$

find

int find(int t, int x)

時刻 t において、要素 x が属する集合の代表元を返します。

制約

$0 \leq x < sz$

計算量

amortized $O(\alpha(sz))$

size

int size(int t, int x)

時刻 t において、要素 x が属する集合の要素数を返します。

制約

$0 \leq x < sz$

計算量

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

Verified with

test/unittest/union-finds.test.cpp

Code

#pragma once

#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>

struct PartiallyPersistentUnionFind {
  std::vector<int> data;
  std::vector<int> last;
  std::vector<std::vector<std::pair<int, int>>> add;

  PartiallyPersistentUnionFind() {}

  PartiallyPersistentUnionFind(int sz) : data(sz, -1), last(sz, 1e9), add(sz) {
    for (auto& vs : add) vs.emplace_back(-1, -1);
  }

  bool unite(int t, int x, int y) {
    x = find(t, x);
    y = find(t, y);
    if (x == y) return false;
    if (data[x] > data[y]) std::swap(x, y);
    data[x] += data[y];
    add[x].emplace_back(t, data[x]);
    data[y] = x;
    last[y] = t;
    return true;
  }

  int find(int t, int x) {
    if (t < last[x]) return x;
    return find(t, data[x]);
  }

  int size(int t, int x) {
    x = find(t, x);
    return -std::prev(std::lower_bound(add[x].begin(), add[x].end(),
                                       std::make_pair(t, 0)))
                ->second;
  }
};

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

#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>

struct PartiallyPersistentUnionFind {
  std::vector<int> data;
  std::vector<int> last;
  std::vector<std::vector<std::pair<int, int>>> add;

  PartiallyPersistentUnionFind() {}

  PartiallyPersistentUnionFind(int sz) : data(sz, -1), last(sz, 1e9), add(sz) {
    for (auto& vs : add) vs.emplace_back(-1, -1);
  }

  bool unite(int t, int x, int y) {
    x = find(t, x);
    y = find(t, y);
    if (x == y) return false;
    if (data[x] > data[y]) std::swap(x, y);
    data[x] += data[y];
    add[x].emplace_back(t, data[x]);
    data[y] = x;
    last[y] = t;
    return true;
  }

  int find(int t, int x) {
    if (t < last[x]) return x;
    return find(t, data[x]);
  }

  int size(int t, int x) {
    x = find(t, x);
    return -std::prev(std::lower_bound(add[x].begin(), add[x].end(),
                                       std::make_pair(t, 0)))
                ->second;
  }
};