Persistent Union Find (data_structure/persistent_unionfind.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-06-22 16:22:13+09:00
• Include: #include "data_structure/persistent_unionfind.hpp"

更新前の状態を保持したまま集合の併合や判定ができる Union-Find です。各更新操作 (merge) は新しいバージョンの Union-Find を生成します。

使い方

コンストラクタ

PersistentUnionfind()
PersistentUnionfind(int n)

説明

指定された要素数を持つ Persistent Union-Find を構築します。最初は各要素がそれぞれ異なる集合に属しています。

• n: 要素数。

計算量

$O(N)$

merge

int merge(int a, int b, int t = -1)

説明

指定されたバージョン t の Union-Find において、要素 a と要素 b が属する集合を併合し、新しいバージョンを生成します。a と b が既に同じ集合に属している場合は何も行いません。t を指定しない場合、最新のバージョンに対して操作を行います。

• a: 要素のインデックス (0-indexed)。
• b: 要素のインデックス (0-indexed)。
• t: 操作を行う Union-Find のバージョンインデックス。-1 の場合は最新バージョン。
• 戻り値: 新しいバージョンのインデックス。

制約

$0 \le a < n$
$0 \le b < n$
$0 \le t < \text{バージョン数}$

計算量

$O(\log N)$

same

bool same(int a, int b, int t = -1)

説明

指定されたバージョン t の Union-Find において、要素 a と要素 b が同じ集合に属しているかを判定します。t を指定しない場合、最新のバージョンに対して操作を行います。

• a: 要素のインデックス (0-indexed)。
• b: 要素のインデックス (0-indexed)。
• t: 判定を行う Union-Find のバージョンインデックス。-1 の場合は最新バージョン。
• 戻り値: a と b が同じ集合に属していれば true、そうでなければ false。

制約

$0 \le a < n$
$0 \le b < n$
$0 \le t < \text{バージョン数}$

計算量

$O(\log N)$

leader

int leader(int a, int t = -1)

説明

指定されたバージョン t の Union-Find において、要素 a が属する集合の代表元を返します。t を指定しない場合、最新のバージョンに対して操作を行います。

• a: 要素のインデックス (0-indexed)。
• t: 代表元を取得する Union-Find のバージョンインデックス。-1 の場合は最新バージョン。
• 戻り値: 要素 a が属する集合の代表元のインデックス。

制約

$0 \le a < n$
$0 \le t < \text{バージョン数}$

計算量

$O(\log N)$

size

int size(int a, int t = -1)

説明

指定されたバージョン t の Union-Find において、要素 a が属する集合の要素数を返します。t を指定しない場合、最新のバージョンに対して操作を行います。

• a: 要素のインデックス (0-indexed)。
• t: サイズを取得する Union-Find のバージョンインデックス。-1 の場合は最新バージョン。
• 戻り値: 要素 a が属する集合のサイズ。

制約

$0 \le a < n$
$0 \le t < \text{バージョン数}$

計算量

$O(\log N)$

Depends on

• Persistent Array (data_structure/persistent_array.hpp)

Verified with

• test/persistent_unionfind.test.cpp

Code

#pragma once
#include <algorithm>
#include <data_structure/persistent_array.hpp>

struct PersistentUnionFind {
    int n;
    PersistentArray<int> v;

    PersistentUnionFind() : n(0), v(0) {}
    explicit PersistentUnionFind(int n) : n(n), v(n, -1) {}

    int merge(int a, int b, int t = -1) {
        int x = leader(a, t), y = leader(b, t);
        if (x == y) return static_cast<int>(v.root.size()) - 1;
        if (-v.get(x, t) < -v.get(y, t)) std::swap(x, y);
        t = v.set(x, v.get(x, t) + v.get(y, t), t);
        return v.set(y, x, t);
    }

    bool same(int a, int b, int t = -1) {
        return leader(a, t) == leader(b, t);
    }

    int leader(int a, int t = -1) {
        if (v.get(a, t) < 0) return a;
        return leader(v.get(a, t), t);
    }

    int size(int a, int t = -1) {
        return -v.get(a, t);
    }
};

#line 2 "data_structure/persistent_unionfind.hpp"
#include <algorithm>
#include <data_structure/persistent_array.hpp>

struct PersistentUnionFind {
    int n;
    PersistentArray<int> v;

    PersistentUnionFind() : n(0), v(0) {}
    explicit PersistentUnionFind(int n) : n(n), v(n, -1) {}

    int merge(int a, int b, int t = -1) {
        int x = leader(a, t), y = leader(b, t);
        if (x == y) return static_cast<int>(v.root.size()) - 1;
        if (-v.get(x, t) < -v.get(y, t)) std::swap(x, y);
        t = v.set(x, v.get(x, t) + v.get(y, t), t);
        return v.set(y, x, t);
    }

    bool same(int a, int b, int t = -1) {
        return leader(a, t) == leader(b, t);
    }

    int leader(int a, int t = -1) {
        if (v.get(a, t) < 0) return a;
        return leader(v.get(a, t), t);
    }

    int size(int a, int t = -1) {
        return -v.get(a, t);
    }
};

Back to top page