Potentialized Unionfind（重み付き Unionfind）
(unionfind/potentialized_unionfind.hpp)

• View this file on GitHub
• Last update: 2025-12-10 04:21:17+09:00
• Include: #include "unionfind/potentialized_unionfind.hpp"

通常の Unionfind に加えて、各頂点に対して「代表元からの重み（ポテンシャル）の差分」を管理するデータ構造です。

• 辺の追加（重み付き）
• $2$ 頂点が連結かの判定
• $2$ 頂点のポテンシャルの差分の取得

をならし $O(\alpha(n))$ 時間で処理することが出来ます。

テンプレート引数として、可換群（アーベル群） $(T, \cdot)$ を G として受け取ります。 可換群とは以下の条件を満たす代数構造です。

• 結合律（ $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ ）が成立する。
• 単位元（ $a \cdot e=e \cdot a=a$ となる $e$ ）が存在する。
• 逆元（ $a \cdot a^{-1}=a^{-1} \cdot a=e$ となる $a^{-1}$ ）が存在する。
• 可換（ $a \cdot b=b \cdot a$ ）である。

例えば、$\cdot$ として和を計算する可換群は ここ に定義されています。

計算量は $\cdot$, $e$, $a^{-1}$ が定数時間で計算できると仮定したときのものを記述します。

コンストラクタ

PotentializedUnionfind<G> uf(int n)

$n$ 頂点 $0$ 辺の無向グラフを作ります。

計算量

• $O(n)$

merge

int uf.merge(int x, int y, T d)

$p_x, p_y$ をそれぞれ $x, y$ のポテンシャルとし、重み $d = p_y \cdot p_x^{-1}$ の辺 $(x, y)$ を足します。

$x, y$ が連結で、かつ重み $d$ で矛盾が生じない場合はその代表元を、$x, y$ が非連結だった場合は新たな代表元を返します。 すなわち、辺の追加により連結成分がマージされる時、新たな代表元は元の連結成分の代表元のうちどちらかになります。

$x, y$ が連結で、かつ重み $d$ で矛盾が生じる場合、$-1$ を返します。

制約

• $0 \leq x < n$
• $0 \leq y < n$

計算量

• ならし $O(\alpha(n))$

same

bool uf.same(int x, int y)

頂点 $x, y$ が連結かどうかを返します。

制約

• $0 \leq x < n$
• $0 \leq y < n$

計算量

• ならし $O(\alpha(n))$

leader

int uf.leader(int x)

頂点 $x$ の属する連結成分の代表元を返します。

制約

• $0 \leq x < n$

計算量

• ならし $O(\alpha(n))$

size

int uf.size(int x)

頂点 $x$ の属する連結成分のサイズを返します。

制約

• $0 \leq x < n$

計算量

• ならし $O(\alpha(n))$

potential

T uf.potential(int x)

頂点 $x$ の属する連結成分の代表元からのポテンシャルの差分を返します。

制約

• $0 \leq x < n$

計算量

• ならし $O(\alpha(n))$

distance

T uf.distance(int x, int y)

$p_x, p_y$ をそれぞれ $x, y$ のポテンシャルとし、$p_y \cdot p_x^{-1}$ を返します。

制約

• $0 \leq x < n$
• $0 \leq y < n$
• $x$ と $y$ が同じ連結成分に属する

計算量

• ならし $O(\alpha(n))$

groups

std::vector<std::vector<std::pair<int, T>>> uf.groups()

グラフを連結成分に分け、その情報を返します。

返り値は「「一つの連結成分の「頂点番号と代表元からのポテンシャルの差分」のリスト」のリスト」です。 （内側外側限らず）std::vector 内でどの順番で格納されているかは未定義です。

計算量

• $O(n)$

Verified with

• unionfind/test/potentialized_unionfind.test.cpp
• unionfind/test/potentialized_unionfind_groups.test.cpp

Code

#pragma once

#include <algorithm>
#include <cassert>
#include <vector>

// Potentialized Unionfind
template <class G> struct PotentializedUnionfind {
    static_assert(G::commutative == true);

    using T = typename G::value_type;

    int n;
    std::vector<int> parent;
    std::vector<T> value;

    PotentializedUnionfind() = default;

    explicit PotentializedUnionfind(int n)
        : n(n), parent(n, -1), value(n, G::identity()) {}

    int leader(int x) {
        assert(0 <= x and x < n);
        if (parent[x] < 0) {
            return x;
        } else {
            int r = leader(parent[x]);
            value[x] = G::operation(value[x], value[parent[x]]);
            return parent[x] = r;
        }
    }

    T potential(int x) {
        assert(0 <= x and x < n);
        leader(x);
        return value[x];
    }

    int merge(int x, int y, T d) {
        assert(0 <= x and x < n);
        assert(0 <= y and y < n);
        // d は y の x からのポテンシャルの差分
        // d を leader(y) の leader(x) からのポテンシャルの差分に修正
        d = G::operation(G::operation(d, potential(x)),
                         G::inverse(potential(y)));
        x = leader(x);
        y = leader(y);
        if (x == y) {
            if (d == G::identity()) {
                return x;
            } else {
                return -1;
            }
        }
        if (-parent[x] < -parent[y]) {
            std::swap(x, y);
            d = G::inverse(d);
        }
        parent[x] += parent[y];
        parent[y] = x;
        value[y] = d;
        return x;
    }

    T distance(int x, int y) {
        assert(0 <= x and x < n);
        assert(0 <= y and y < n);
        assert(same(x, y));
        return G::operation(potential(y), G::inverse(potential(x)));
    }

    bool same(int x, int y) {
        assert(0 <= x and x < n);
        assert(0 <= y and y < n);
        return leader(x) == leader(y);
    }

    int size(int x) {
        assert(0 <= x and x < n);
        return -parent[leader(x)];
    }

    std::vector<std::vector<std::pair<int, T>>> groups() {
        std::vector<int> leader_buf(n), group_size(n);
        for (int i = 0; i < n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<std::pair<int, T>>> result(n);
        for (int i = 0; i < n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < n; i++) {
            result[leader_buf[i]].emplace_back(i, potential(i));
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<std::pair<int, T>>& v) {
                               return v.empty();
                           }),
            result.end());
        return result;
    }
};

#line 2 "unionfind/potentialized_unionfind.hpp"

#include <algorithm>
#include <cassert>
#include <vector>

// Potentialized Unionfind
template <class G> struct PotentializedUnionfind {
    static_assert(G::commutative == true);

    using T = typename G::value_type;

    int n;
    std::vector<int> parent;
    std::vector<T> value;

    PotentializedUnionfind() = default;

    explicit PotentializedUnionfind(int n)
        : n(n), parent(n, -1), value(n, G::identity()) {}

    int leader(int x) {
        assert(0 <= x and x < n);
        if (parent[x] < 0) {
            return x;
        } else {
            int r = leader(parent[x]);
            value[x] = G::operation(value[x], value[parent[x]]);
            return parent[x] = r;
        }
    }

    T potential(int x) {
        assert(0 <= x and x < n);
        leader(x);
        return value[x];
    }

    int merge(int x, int y, T d) {
        assert(0 <= x and x < n);
        assert(0 <= y and y < n);
        // d は y の x からのポテンシャルの差分
        // d を leader(y) の leader(x) からのポテンシャルの差分に修正
        d = G::operation(G::operation(d, potential(x)),
                         G::inverse(potential(y)));
        x = leader(x);
        y = leader(y);
        if (x == y) {
            if (d == G::identity()) {
                return x;
            } else {
                return -1;
            }
        }
        if (-parent[x] < -parent[y]) {
            std::swap(x, y);
            d = G::inverse(d);
        }
        parent[x] += parent[y];
        parent[y] = x;
        value[y] = d;
        return x;
    }

    T distance(int x, int y) {
        assert(0 <= x and x < n);
        assert(0 <= y and y < n);
        assert(same(x, y));
        return G::operation(potential(y), G::inverse(potential(x)));
    }

    bool same(int x, int y) {
        assert(0 <= x and x < n);
        assert(0 <= y and y < n);
        return leader(x) == leader(y);
    }

    int size(int x) {
        assert(0 <= x and x < n);
        return -parent[leader(x)];
    }

    std::vector<std::vector<std::pair<int, T>>> groups() {
        std::vector<int> leader_buf(n), group_size(n);
        for (int i = 0; i < n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<std::pair<int, T>>> result(n);
        for (int i = 0; i < n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < n; i++) {
            result[leader_buf[i]].emplace_back(i, potential(i));
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<std::pair<int, T>>& v) {
                               return v.empty();
                           }),
            result.end());
        return result;
    }
};

Back to top page