Potentialized DSU
(ds/dsu/potentialized_dsu.hpp)

View this file on GitHub
Last update: 2026-07-16 20:44:54+09:00
Include: #include "ds/dsu/potentialized_dsu.hpp"

Overview

PotentializedDsu is a weighted Union-Find over a possibly noncommutative group. It stores relative potentials inside each connected component and can answer potential differences between two vertices.

The template parameter is a type satisfying m1une::monoid::IsGroup, so the same data structure works with addition, xor, matrix multiplication, permutation composition, and other group operations.

The main operation is merge(a, b, w), which adds the constraint diff(a, b) == w. Here diff(a, b) is defined as Group::op(Group::inv(potential(a)), potential(b)).

The order of these operations is significant. If P(v) = potential(v), then merge(a, b, w) imposes

inv(P(a)) * P(b) = w

or equivalently P(b) = P(a) * w, where * denotes Group::op. Reversing the arguments of merge therefore requires both swapping the vertices and inverting w.

For m1une::monoid::Add<long long>, this means:

potential(b) - potential(a) == w

Equivalently, diff(a, b) is b - a for addition.

For m1une::monoid::Xor<int>, this means:

potential(a) ^ potential(b) == w

Absolute values returned by potential(v) are root-relative and may shift when components are merged. Use diff(a, b) for stable values.

Template Parameters

Group: A type satisfying m1une::monoid::IsGroup.

The group must provide:

using value_type = T
static T id()
static T op(const T& a, const T& b)
static T inv(const T& x)

T must be equality comparable so repeated constraints can be checked for consistency.

Methods

Method	Description	Complexity
`PotentializedDsu()`	Creates an empty DSU.	$O(1)$
`explicit PotentializedDsu(int n)`	Creates `n` singleton sets with identity potentials.	$O(N)$
`int size() const`	Returns the number of elements.	$O(1)$
`bool empty() const`	Returns whether the DSU has no elements.	$O(1)$
`bool merge(int a, int b, const T& w)`	Adds the constraint `diff(a, b) == w`. Returns `false` only when `a` and `b` were already connected and the constraint contradicts the stored potentials.	Amortized $O(\alpha(N))$
`bool same(int a, int b)`	Returns whether `a` and `b` are in the same set and applies path compression.	Amortized $O(\alpha(N))$
`bool same(int a, int b) const`	Returns whether `a` and `b` are in the same set without mutation.	$O(\log N)$
`int leader(int a)`	Returns the representative and applies path compression.	Amortized $O(\alpha(N))$
`int leader(int a) const`	Returns the representative without mutation.	$O(\log N)$
`int group_size(int a)`, `int size(int a)`	Returns the component size and applies path compression.	Amortized $O(\alpha(N))$
`int group_size(int a) const`, `int size(int a) const`	Returns the component size without mutation.	$O(\log N)$
`T potential(int a)`	Returns the root-relative potential and applies path compression.	Amortized $O(\alpha(N))$
`T potential(int a) const`	Returns the root-relative potential without mutation.	$O(\log N)$
`T diff(int a, int b)`	Returns the potential difference from `a` to `b` and applies path compression. Requires `same(a, b)`.	Amortized $O(\alpha(N))$
`T diff(int a, int b) const`	Returns the potential difference without mutation. Requires `same(a, b)`.	$O(\log N)$
`std::vector<std::vector<int>> groups()`	Returns all components and applies path compression.	$O(N \alpha(N))$
`std::vector<std::vector<int>> groups() const`	Returns all components without mutation.	$O(N \log N)$

Example

#include "ds/dsu/potentialized_dsu.hpp"
#include <array>

#include <iostream>

struct Permutation3 {
    using value_type = std::array<int, 3>;

    static value_type id() {
        return {0, 1, 2};
    }

    static value_type op(const value_type& first, const value_type& second) {
        value_type result;
        for (int i = 0; i < 3; i++) result[i] = second[first[i]];
        return result;
    }

    static value_type inv(const value_type& value) {
        value_type result;
        for (int i = 0; i < 3; i++) result[value[i]] = i;
        return result;
    }
};

int main() {
    using P = Permutation3::value_type;
    m1une::ds::PotentializedDsu<Permutation3> dsu(3);

    P rotate = {1, 2, 0};
    P swap_last = {0, 2, 1};
    dsu.merge(0, 1, rotate);
    dsu.merge(1, 2, swap_last);

    P composed = dsu.diff(0, 2);
    for (int image : composed) std::cout << image << ' ';
    std::cout << '\n';
}

Depends on

Monoid Concept (monoid/concept.hpp)

Verified with

Code

#ifndef M1UNE_POTENTIALIZED_DSU_HPP
#define M1UNE_POTENTIALIZED_DSU_HPP 1

#include <algorithm>
#include <cassert>
#include <concepts>
#include <utility>
#include <vector>

#include "../../monoid/concept.hpp"

namespace m1une {
namespace ds {

template <m1une::monoid::IsGroup Group>
requires std::equality_comparable<typename Group::value_type>
struct PotentializedDsu {
    using T = typename Group::value_type;

   private:
    int _n;
    std::vector<int> parent_or_size;
    std::vector<T> diff_to_parent;

    static int check_size(int n) {
        assert(0 <= n);
        return n;
    }

   public:
    PotentializedDsu() : PotentializedDsu(0) {}

    explicit PotentializedDsu(int n) : _n(check_size(n)), parent_or_size(_n, -1), diff_to_parent(_n, Group::id()) {}

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        int p = parent_or_size[a];
        int r = leader(p);
        diff_to_parent[a] = Group::op(diff_to_parent[p], diff_to_parent[a]);
        return parent_or_size[a] = r;
    }

    int leader(int a) const {
        assert(0 <= a && a < _n);
        while (parent_or_size[a] >= 0) a = parent_or_size[a];
        return a;
    }

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

    bool same(int a, int b) const {
        return leader(a) == leader(b);
    }

    int group_size(int a) {
        return -parent_or_size[leader(a)];
    }

    int group_size(int a) const {
        return -parent_or_size[leader(a)];
    }

    int size(int a) {
        return group_size(a);
    }

    int size(int a) const {
        return group_size(a);
    }

    T potential(int a) {
        leader(a);
        return diff_to_parent[a];
    }

    T potential(int a) const {
        assert(0 <= a && a < _n);
        T res = Group::id();
        while (parent_or_size[a] >= 0) {
            res = Group::op(diff_to_parent[a], res);
            a = parent_or_size[a];
        }
        return res;
    }

    T diff(int a, int b) {
        assert(same(a, b));
        return Group::op(Group::inv(potential(a)), potential(b));
    }

    T diff(int a, int b) const {
        assert(same(a, b));
        return Group::op(Group::inv(potential(a)), potential(b));
    }

    bool merge(int a, int b, const T& w) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a);
        int y = leader(b);
        T pa = diff_to_parent[a], pb = diff_to_parent[b];
        if (x == y) return Group::op(Group::inv(pa), pb) == w;

        T y_from_x = Group::op(Group::op(pa, w), Group::inv(pb));
        if (-parent_or_size[x] < -parent_or_size[y]) {
            std::swap(x, y);
            y_from_x = Group::inv(y_from_x);
        }
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        diff_to_parent[y] = std::move(y_from_x);
        return true;
    }

    std::vector<std::vector<int>> 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<int>> 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]].push_back(i);
        }
        result.erase(std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }),
                     result.end());
        return result;
    }

    std::vector<std::vector<int>> groups() const {
        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<int>> 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]].push_back(i);
        }
        result.erase(std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }),
                     result.end());
        return result;
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_POTENTIALIZED_DSU_HPP

#line 1 "ds/dsu/potentialized_dsu.hpp"



#include <algorithm>
#include <cassert>
#include <concepts>
#include <utility>
#include <vector>

#line 1 "monoid/concept.hpp"



#line 5 "monoid/concept.hpp"

namespace m1une {
namespace monoid {

// Concept to check if a type satisfies the requirements of a Monoid.
// A Monoid must have a `value_type`, an identity element `id()`, and an associative binary operation `op()`.
template <typename M>
concept IsMonoid = requires(typename M::value_type a, typename M::value_type b) {
    // 1. Must define `value_type`
    typename M::value_type;

    // 2. Must have a static method `id()` returning `value_type`
    { M::id() } -> std::same_as<typename M::value_type>;

    // 3. Must have a static method `op(a, b)` returning `value_type`
    { M::op(a, b) } -> std::same_as<typename M::value_type>;
};

// Concept for groups. A type satisfying this concept must also obey the group
// laws; concepts can check the interface but not the algebraic properties.
template <typename M>
concept IsGroup = IsMonoid<M> && requires(typename M::value_type a) {
    { M::inv(a) } -> std::same_as<typename M::value_type>;
};

// Concept for commutative groups. Commutativity is a semantic requirement and
// cannot be checked by a C++ concept.
template <typename M>
concept IsCommutativeGroup = IsGroup<M>;

}  // namespace monoid
}  // namespace m1une


#line 11 "ds/dsu/potentialized_dsu.hpp"

namespace m1une {
namespace ds {

template <m1une::monoid::IsGroup Group>
requires std::equality_comparable<typename Group::value_type>
struct PotentializedDsu {
    using T = typename Group::value_type;

   private:
    int _n;
    std::vector<int> parent_or_size;
    std::vector<T> diff_to_parent;

    static int check_size(int n) {
        assert(0 <= n);
        return n;
    }

   public:
    PotentializedDsu() : PotentializedDsu(0) {}

    explicit PotentializedDsu(int n) : _n(check_size(n)), parent_or_size(_n, -1), diff_to_parent(_n, Group::id()) {}

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        int p = parent_or_size[a];
        int r = leader(p);
        diff_to_parent[a] = Group::op(diff_to_parent[p], diff_to_parent[a]);
        return parent_or_size[a] = r;
    }

    int leader(int a) const {
        assert(0 <= a && a < _n);
        while (parent_or_size[a] >= 0) a = parent_or_size[a];
        return a;
    }

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

    bool same(int a, int b) const {
        return leader(a) == leader(b);
    }

    int group_size(int a) {
        return -parent_or_size[leader(a)];
    }

    int group_size(int a) const {
        return -parent_or_size[leader(a)];
    }

    int size(int a) {
        return group_size(a);
    }

    int size(int a) const {
        return group_size(a);
    }

    T potential(int a) {
        leader(a);
        return diff_to_parent[a];
    }

    T potential(int a) const {
        assert(0 <= a && a < _n);
        T res = Group::id();
        while (parent_or_size[a] >= 0) {
            res = Group::op(diff_to_parent[a], res);
            a = parent_or_size[a];
        }
        return res;
    }

    T diff(int a, int b) {
        assert(same(a, b));
        return Group::op(Group::inv(potential(a)), potential(b));
    }

    T diff(int a, int b) const {
        assert(same(a, b));
        return Group::op(Group::inv(potential(a)), potential(b));
    }

    bool merge(int a, int b, const T& w) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a);
        int y = leader(b);
        T pa = diff_to_parent[a], pb = diff_to_parent[b];
        if (x == y) return Group::op(Group::inv(pa), pb) == w;

        T y_from_x = Group::op(Group::op(pa, w), Group::inv(pb));
        if (-parent_or_size[x] < -parent_or_size[y]) {
            std::swap(x, y);
            y_from_x = Group::inv(y_from_x);
        }
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        diff_to_parent[y] = std::move(y_from_x);
        return true;
    }

    std::vector<std::vector<int>> 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<int>> 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]].push_back(i);
        }
        result.erase(std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }),
                     result.end());
        return result;
    }

    std::vector<std::vector<int>> groups() const {
        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<int>> 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]].push_back(i);
        }
        result.erase(std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }),
                     result.end());
        return result;
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Potentialized DSU
(ds/dsu/potentialized_dsu.hpp)

Overview

Template Parameters

Methods

Example

Depends on

Verified with

Code

Potentialized DSU (ds/dsu/potentialized_dsu.hpp)

Overview

Template Parameters

Methods

Example

Depends on

Verified with

Code

Potentialized DSU
(ds/dsu/potentialized_dsu.hpp)