Persistent Potentialized DSU
(ds/dsu/persistent_potentialized_dsu.hpp)

View this file on GitHub
Last update: 2026-08-12 03:11:00+09:00
Include: #include "ds/dsu/persistent_potentialized_dsu.hpp"

Overview

PersistentPotentializedDsu is a persistent weighted Union-Find over a possibly noncommutative group. Merge operations return a new version and leave the old version available, while preserving potential differences inside each component.

Reference counting recycles internal persistent-array nodes after their final dependent version and parent are released.

merge returns a new version. merge_inplace applies the same constraint to this handle with copy-on-write, preserving other live versions and reusing unique persistent-array paths. Its return value reports consistency, like the bool in the result of merge.

The template parameter is a type satisfying m1une::monoid::IsGroup. The stored constraint for merge(a, b, w) is diff(a, b) == w, where diff(a, b) is Group::op(Group::inv(potential(a)), potential(b)).

Operation order is significant: if P(v) = potential(v), the constraint is inv(P(a)) * P(b) = w, or equivalently P(b) = P(a) * w.

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

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

Absolute values returned by potential(v) are root-relative. Use diff(a, b) for stable values.

Complexity Notation

N is the number of elements.

Template Parameters

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

The group value type must be equality comparable so repeated constraints can be checked for consistency.

Methods

Method	Description	Complexity
`PersistentPotentializedDsu()`	Creates an empty DSU.	$O(1)$
`explicit PersistentPotentializedDsu(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)$
`void release()`	Releases this version immediately and makes this handle empty.	$O(F)$
`std::size_t node_count() const`	Returns live internal nodes in the shared version family.	$O(1)$
`std::pair<PersistentPotentializedDsu, bool> merge(int a, int b, const T& w) const`	Returns a new version with the constraint `diff(a, b) == w`, and whether the constraint is consistent. If the constraint contradicts an existing component, the returned version is unchanged.	$O(\log^2 N)$
`bool merge_inplace(int a, int b, const T& w)`	Adds the constraint to this version using copy-on-write and returns whether it is consistent. A contradiction leaves this version unchanged.	$O(\log^2 N)$
`bool same(int a, int b) const`	Returns whether `a` and `b` are in the same set.	$O(\log^2 N)$
`int leader(int a) const`	Returns the representative of the set containing `a`.	$O(\log^2 N)$
`int group_size(int a) const`, `int size(int a) const`	Returns the size of the set containing `a`.	$O(\log^2 N)$
`T potential(int a) const`	Returns the root-relative potential of `a`.	$O(\log^2 N)$
`T diff(int a, int b) const`	Returns the potential difference from `a` to `b`. Requires `same(a, b)`.	$O(\log^2 N)$
`Value get(int p) const`	Returns the internal value at index `p`. It has `parent_or_size` and `diff_to_parent` members.	$O(\log N)$
`int parent_or_size(int p) const`	Returns the internal parent-or-size value at index `p`.	$O(\log N)$
`std::vector<std::vector<int>> groups() const`	Returns all sets as vectors of element indices.	$O(N \log^2 N)$

Here $F$ is the number of internal nodes that become unreachable. Destruction and assignment release roots automatically.

Example

#include "ds/dsu/persistent_potentialized_dsu.hpp"
#include "monoid/add.hpp"

#include <iostream>

int main() {
    using Add = m1une::monoid::Add<long long>;
    using Dsu = m1une::ds::PersistentPotentializedDsu<Add>;

    Dsu dsu(3);

    auto [a, ok1] = dsu.merge(0, 1, 3);
    auto [b, ok2] = a.merge(1, 2, 4);
    auto [bad, ok3] = b.merge(0, 2, 8);

    std::cout << ok1 << "\n";          // 1
    std::cout << ok2 << "\n";          // 1
    std::cout << ok3 << "\n";          // 0
    std::cout << dsu.same(0, 2) << "\n"; // 0
    std::cout << b.diff(0, 2) << "\n"; // 7
}

Depends on

Verified with

Code

#ifndef M1UNE_PERSISTENT_POTENTIALIZED_DSU_HPP
#define M1UNE_PERSISTENT_POTENTIALIZED_DSU_HPP 1

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

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

namespace m1une {
namespace ds {

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

    struct Value {
        int parent_or_size;
        T diff_to_parent;

        Value() : parent_or_size(0), diff_to_parent(Group::id()) {}
        Value(int parent_or_size_, const T& diff_to_parent_)
            : parent_or_size(parent_or_size_), diff_to_parent(diff_to_parent_) {}
        Value(int parent_or_size_, T&& diff_to_parent_)
            : parent_or_size(parent_or_size_), diff_to_parent(std::move(diff_to_parent_)) {}
    };

   private:
    struct Node {
        Value val;
        int l, r;

        Node() : val(), l(0), r(0) {}
        explicit Node(const Value& value) : val(value), l(0), r(0) {}
        explicit Node(Value&& value) : val(std::move(value)), l(0), r(0) {}
        Node(const Value& value, int left, int right) : val(value), l(left), r(right) {}
        Node(Value&& value, int left, int right) : val(std::move(value)), l(left), r(right) {}
    };

    int _n;
    int _root;
    using Pool = detail::PersistentBinaryNodePool<Node, 0>;

    std::shared_ptr<Pool> _pool;

    explicit PersistentPotentializedDsu(int n, int root, std::shared_ptr<Pool> pool)
        : _n(n), _root(root), _pool(std::move(pool)) {
        _pool->retain(_root);
    }

    int new_node(const Node& node) const {
        return _pool->emplace(node);
    }

    int new_node(Node&& node) const {
        return _pool->emplace(std::move(node));
    }

    int build(int l, int r) const {
        if (l == r) return 0;
        if (r - l == 1) return new_node(Node(Value(-1, Group::id())));
        int m = (l + r) >> 1;
        int left = build(l, m);
        int right = build(m, r);
        return new_node(Node(Value(), left, right));
    }

    int set_node(int t, int l, int r, int p, Value value, bool copy_on_write = false) const {
        if (copy_on_write) t = _pool->clone_if_shared(t);
        if (r - l == 1) {
            if (copy_on_write) {
                (*_pool)[t].val = std::move(value);
                return t;
            }
            return new_node(Node(std::move(value)));
        }
        int m = (l + r) >> 1;
        int left = (*_pool)[t].l;
        int right = (*_pool)[t].r;
        if (p < m) {
            left = set_node(left, l, m, p, std::move(value), copy_on_write);
        } else {
            right = set_node(right, m, r, p, std::move(value), copy_on_write);
        }
        if (copy_on_write) {
            _pool->replace((*_pool)[t].l, left);
            _pool->replace((*_pool)[t].r, right);
            return t;
        }
        return new_node(Node(Value(), left, right));
    }

    Value get_value(int t, int l, int r, int p) const {
        while (r - l > 1) {
            int m = (l + r) >> 1;
            if (p < m) {
                t = (*_pool)[t].l;
                r = m;
            } else {
                t = (*_pool)[t].r;
                l = m;
            }
        }
        return (*_pool)[t].val;
    }

    std::pair<int, T> leader_and_potential(int a) const {
        T res = Group::id();
        while (true) {
            Value cur = get(a);
            if (cur.parent_or_size < 0) return {a, res};
            res = Group::op(cur.diff_to_parent, res);
            a = cur.parent_or_size;
        }
    }

    PersistentPotentializedDsu make_version(int root) const {
        PersistentPotentializedDsu result(_n, root, _pool);
        _pool->discard_unreferenced();
        return result;
    }

   public:
    PersistentPotentializedDsu() : PersistentPotentializedDsu(0) {}

    explicit PersistentPotentializedDsu(int n) : _n(n), _root(0), _pool(std::make_shared<Pool>()) {
        assert(0 <= n);
        _pool->reserve(n * 4 + 1);
        if (_n > 0) _root = build(0, _n);
        _pool->retain(_root);
        _pool->discard_unreferenced();
    }

    PersistentPotentializedDsu(const PersistentPotentializedDsu& other)
        : _n(other._n), _root(other._root), _pool(other._pool) {
        if (_pool) _pool->retain(_root);
    }

    PersistentPotentializedDsu(PersistentPotentializedDsu&& other) noexcept
        : _n(other._n), _root(other._root), _pool(std::move(other._pool)) {
        other._n = 0;
        other._root = 0;
    }

    PersistentPotentializedDsu& operator=(const PersistentPotentializedDsu& other) {
        if (this == &other) return *this;
        if (other._pool) other._pool->retain(other._root);
        if (_pool) _pool->release(_root);
        _n = other._n;
        _root = other._root;
        _pool = other._pool;
        return *this;
    }

    PersistentPotentializedDsu& operator=(PersistentPotentializedDsu&& other) noexcept {
        if (this == &other) return *this;
        if (_pool) _pool->release(_root);
        _n = other._n;
        _root = other._root;
        _pool = std::move(other._pool);
        other._n = 0;
        other._root = 0;
        return *this;
    }

    ~PersistentPotentializedDsu() {
        if (_pool) _pool->release(_root);
    }

    int size() const {
        return _n;
    }

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

    void release() {
        if (_pool) _pool->release(_root);
        _n = 0;
        _root = 0;
        _pool = std::make_shared<Pool>();
    }

    std::size_t node_count() const { return _pool ? _pool->size() : 0; }

    int leader(int a) const {
        assert(0 <= a && a < _n);
        return leader_and_potential(a).first;
    }

    bool same(int a, int b) const {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int group_size(int a) const {
        assert(0 <= a && a < _n);
        return -get(leader(a)).parent_or_size;
    }

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

    T potential(int a) const {
        assert(0 <= a && a < _n);
        return leader_and_potential(a).second;
    }

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

    Value get(int p) const {
        assert(0 <= p && p < _n);
        return get_value(_root, 0, _n, p);
    }

    int parent_or_size(int p) const {
        return get(p).parent_or_size;
    }

    std::pair<PersistentPotentializedDsu, bool> merge(int a, int b, const T& w) const {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        auto [x, pa] = leader_and_potential(a);
        auto [y, pb] = leader_and_potential(b);
        if (x == y) return {*this, Group::op(Group::inv(pa), pb) == w};

        int sx = -get(x).parent_or_size;
        int sy = -get(y).parent_or_size;
        T y_from_x = Group::op(Group::op(pa, w), Group::inv(pb));
        if (sx < sy) {
            std::swap(x, y);
            std::swap(sx, sy);
            y_from_x = Group::inv(y_from_x);
        }
        int root = set_node(_root, 0, _n, x, Value(-(sx + sy), Group::id()));
        root = set_node(root, 0, _n, y, Value(x, std::move(y_from_x)));
        return {make_version(root), true};
    }

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

        int sx = -get(x).parent_or_size;
        int sy = -get(y).parent_or_size;
        T y_from_x = Group::op(Group::op(pa, w), Group::inv(pb));
        if (sx < sy) {
            std::swap(x, y);
            std::swap(sx, sy);
            y_from_x = Group::inv(y_from_x);
        }
        int root = set_node(_root, 0, _n, x, Value(-(sx + sy), Group::id()), true);
        _pool->replace(_root, root);
        root = set_node(_root, 0, _n, y, Value(x, std::move(y_from_x)), true);
        _pool->replace(_root, root);
        _pool->discard_unreferenced();
        return true;
    }

    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_PERSISTENT_POTENTIALIZED_DSU_HPP

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



#include <algorithm>
#include <cassert>
#include <concepts>
#include <cstddef>
#include <memory>
#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 1 "ds/detail/persistent_binary_node_pool.hpp"



#line 6 "ds/detail/persistent_binary_node_pool.hpp"
#include <deque>
#include <limits>
#include <optional>
#line 11 "ds/detail/persistent_binary_node_pool.hpp"

namespace m1une {
namespace ds {
namespace detail {

// Node must have integer `l` and `r` members. New nodes initially have no
// owner; discard_unreferenced() removes temporary path-copy nodes after the
// result roots have been retained.
template <class Node, int null_node = -1>
struct PersistentBinaryNodePool {
   private:
    std::deque<std::optional<Node>> _nodes;
    std::vector<int> _references;
    std::vector<int> _next_free;
    std::vector<int> _unowned;
    int _first_free = -1;
    std::size_t _live_nodes = 0;

    void release_zero(int node) {
        assert(node != null_node && _nodes[node].has_value());
        int left = (*_nodes[node]).l;
        int right = (*_nodes[node]).r;
        _nodes[node].reset();
        _next_free[node] = _first_free;
        _first_free = node;
        --_live_nodes;
        if (left != null_node && --_references[left] == 0) release_zero(left);
        if (right != null_node && --_references[right] == 0) release_zero(right);
    }

   public:
    PersistentBinaryNodePool() {
        if constexpr (null_node == 0) {
            _nodes.emplace_back();
            _references.push_back(0);
            _next_free.push_back(-1);
        }
    }

    Node& operator[](int node) {
        assert(node != null_node && _nodes[node].has_value());
        return *_nodes[node];
    }

    const Node& operator[](int node) const {
        assert(node != null_node && _nodes[node].has_value());
        return *_nodes[node];
    }

    template <class... Args>
    int emplace(Args&&... args) {
        int result;
        if (_first_free == -1) {
            assert(_nodes.size() < std::size_t(std::numeric_limits<int>::max()));
            result = int(_nodes.size());
            _nodes.emplace_back(std::in_place, std::forward<Args>(args)...);
            _references.push_back(0);
            _next_free.push_back(-1);
        } else {
            result = _first_free;
            _first_free = _next_free[result];
            _nodes[result].emplace(std::forward<Args>(args)...);
            _references[result] = 0;
        }
        retain((*_nodes[result]).l);
        retain((*_nodes[result]).r);
        _unowned.push_back(result);
        ++_live_nodes;
        return result;
    }

    void retain(int node) {
        if (node != null_node) {
            assert(_nodes[node].has_value());
            ++_references[node];
        }
    }

    void release(int node) {
        if (node == null_node) return;
        assert(_nodes[node].has_value() && _references[node] > 0);
        if (--_references[node] == 0) release_zero(node);
    }

    bool unique(int node) const {
        return node == null_node || _references[node] == 1;
    }

    int clone(int node) {
        assert(node != null_node && _nodes[node].has_value());
        return emplace(*_nodes[node]);
    }

    // Returns node itself when it has one owner, otherwise an unowned clone.
    // A returned clone becomes owned when a root or parent edge retains it.
    int clone_if_shared(int node) {
        if (unique(node)) return node;
        return clone(node);
    }

    void replace(int& edge, int node) {
        if (edge == node) return;
        retain(node);
        int old = edge;
        edge = node;
        release(old);
    }

    void discard_unreferenced() {
        while (!_unowned.empty()) {
            int node = _unowned.back();
            _unowned.pop_back();
            if (_nodes[node].has_value() && _references[node] == 0) release_zero(node);
        }
    }

    void reserve(std::size_t) {}

    int next_index() const { return _first_free == -1 ? int(_nodes.size()) : _first_free; }

    std::size_t size() const { return _live_nodes; }
};

}  // namespace detail
}  // namespace ds
}  // namespace m1une


#line 14 "ds/dsu/persistent_potentialized_dsu.hpp"

namespace m1une {
namespace ds {

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

    struct Value {
        int parent_or_size;
        T diff_to_parent;

        Value() : parent_or_size(0), diff_to_parent(Group::id()) {}
        Value(int parent_or_size_, const T& diff_to_parent_)
            : parent_or_size(parent_or_size_), diff_to_parent(diff_to_parent_) {}
        Value(int parent_or_size_, T&& diff_to_parent_)
            : parent_or_size(parent_or_size_), diff_to_parent(std::move(diff_to_parent_)) {}
    };

   private:
    struct Node {
        Value val;
        int l, r;

        Node() : val(), l(0), r(0) {}
        explicit Node(const Value& value) : val(value), l(0), r(0) {}
        explicit Node(Value&& value) : val(std::move(value)), l(0), r(0) {}
        Node(const Value& value, int left, int right) : val(value), l(left), r(right) {}
        Node(Value&& value, int left, int right) : val(std::move(value)), l(left), r(right) {}
    };

    int _n;
    int _root;
    using Pool = detail::PersistentBinaryNodePool<Node, 0>;

    std::shared_ptr<Pool> _pool;

    explicit PersistentPotentializedDsu(int n, int root, std::shared_ptr<Pool> pool)
        : _n(n), _root(root), _pool(std::move(pool)) {
        _pool->retain(_root);
    }

    int new_node(const Node& node) const {
        return _pool->emplace(node);
    }

    int new_node(Node&& node) const {
        return _pool->emplace(std::move(node));
    }

    int build(int l, int r) const {
        if (l == r) return 0;
        if (r - l == 1) return new_node(Node(Value(-1, Group::id())));
        int m = (l + r) >> 1;
        int left = build(l, m);
        int right = build(m, r);
        return new_node(Node(Value(), left, right));
    }

    int set_node(int t, int l, int r, int p, Value value, bool copy_on_write = false) const {
        if (copy_on_write) t = _pool->clone_if_shared(t);
        if (r - l == 1) {
            if (copy_on_write) {
                (*_pool)[t].val = std::move(value);
                return t;
            }
            return new_node(Node(std::move(value)));
        }
        int m = (l + r) >> 1;
        int left = (*_pool)[t].l;
        int right = (*_pool)[t].r;
        if (p < m) {
            left = set_node(left, l, m, p, std::move(value), copy_on_write);
        } else {
            right = set_node(right, m, r, p, std::move(value), copy_on_write);
        }
        if (copy_on_write) {
            _pool->replace((*_pool)[t].l, left);
            _pool->replace((*_pool)[t].r, right);
            return t;
        }
        return new_node(Node(Value(), left, right));
    }

    Value get_value(int t, int l, int r, int p) const {
        while (r - l > 1) {
            int m = (l + r) >> 1;
            if (p < m) {
                t = (*_pool)[t].l;
                r = m;
            } else {
                t = (*_pool)[t].r;
                l = m;
            }
        }
        return (*_pool)[t].val;
    }

    std::pair<int, T> leader_and_potential(int a) const {
        T res = Group::id();
        while (true) {
            Value cur = get(a);
            if (cur.parent_or_size < 0) return {a, res};
            res = Group::op(cur.diff_to_parent, res);
            a = cur.parent_or_size;
        }
    }

    PersistentPotentializedDsu make_version(int root) const {
        PersistentPotentializedDsu result(_n, root, _pool);
        _pool->discard_unreferenced();
        return result;
    }

   public:
    PersistentPotentializedDsu() : PersistentPotentializedDsu(0) {}

    explicit PersistentPotentializedDsu(int n) : _n(n), _root(0), _pool(std::make_shared<Pool>()) {
        assert(0 <= n);
        _pool->reserve(n * 4 + 1);
        if (_n > 0) _root = build(0, _n);
        _pool->retain(_root);
        _pool->discard_unreferenced();
    }

    PersistentPotentializedDsu(const PersistentPotentializedDsu& other)
        : _n(other._n), _root(other._root), _pool(other._pool) {
        if (_pool) _pool->retain(_root);
    }

    PersistentPotentializedDsu(PersistentPotentializedDsu&& other) noexcept
        : _n(other._n), _root(other._root), _pool(std::move(other._pool)) {
        other._n = 0;
        other._root = 0;
    }

    PersistentPotentializedDsu& operator=(const PersistentPotentializedDsu& other) {
        if (this == &other) return *this;
        if (other._pool) other._pool->retain(other._root);
        if (_pool) _pool->release(_root);
        _n = other._n;
        _root = other._root;
        _pool = other._pool;
        return *this;
    }

    PersistentPotentializedDsu& operator=(PersistentPotentializedDsu&& other) noexcept {
        if (this == &other) return *this;
        if (_pool) _pool->release(_root);
        _n = other._n;
        _root = other._root;
        _pool = std::move(other._pool);
        other._n = 0;
        other._root = 0;
        return *this;
    }

    ~PersistentPotentializedDsu() {
        if (_pool) _pool->release(_root);
    }

    int size() const {
        return _n;
    }

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

    void release() {
        if (_pool) _pool->release(_root);
        _n = 0;
        _root = 0;
        _pool = std::make_shared<Pool>();
    }

    std::size_t node_count() const { return _pool ? _pool->size() : 0; }

    int leader(int a) const {
        assert(0 <= a && a < _n);
        return leader_and_potential(a).first;
    }

    bool same(int a, int b) const {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int group_size(int a) const {
        assert(0 <= a && a < _n);
        return -get(leader(a)).parent_or_size;
    }

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

    T potential(int a) const {
        assert(0 <= a && a < _n);
        return leader_and_potential(a).second;
    }

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

    Value get(int p) const {
        assert(0 <= p && p < _n);
        return get_value(_root, 0, _n, p);
    }

    int parent_or_size(int p) const {
        return get(p).parent_or_size;
    }

    std::pair<PersistentPotentializedDsu, bool> merge(int a, int b, const T& w) const {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        auto [x, pa] = leader_and_potential(a);
        auto [y, pb] = leader_and_potential(b);
        if (x == y) return {*this, Group::op(Group::inv(pa), pb) == w};

        int sx = -get(x).parent_or_size;
        int sy = -get(y).parent_or_size;
        T y_from_x = Group::op(Group::op(pa, w), Group::inv(pb));
        if (sx < sy) {
            std::swap(x, y);
            std::swap(sx, sy);
            y_from_x = Group::inv(y_from_x);
        }
        int root = set_node(_root, 0, _n, x, Value(-(sx + sy), Group::id()));
        root = set_node(root, 0, _n, y, Value(x, std::move(y_from_x)));
        return {make_version(root), true};
    }

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

        int sx = -get(x).parent_or_size;
        int sy = -get(y).parent_or_size;
        T y_from_x = Group::op(Group::op(pa, w), Group::inv(pb));
        if (sx < sy) {
            std::swap(x, y);
            std::swap(sx, sy);
            y_from_x = Group::inv(y_from_x);
        }
        int root = set_node(_root, 0, _n, x, Value(-(sx + sy), Group::id()), true);
        _pool->replace(_root, root);
        root = set_node(_root, 0, _n, y, Value(x, std::move(y_from_x)), true);
        _pool->replace(_root, root);
        _pool->discard_unreferenced();
        return true;
    }

    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

Persistent Potentialized DSU
(ds/dsu/persistent_potentialized_dsu.hpp)

Overview

Complexity Notation

Template Parameters

Methods

Example

Depends on

Verified with

Code

Persistent Potentialized DSU (ds/dsu/persistent_potentialized_dsu.hpp)

Overview

Complexity Notation

Template Parameters

Methods

Example

Depends on

Verified with

Code

Persistent Potentialized DSU
(ds/dsu/persistent_potentialized_dsu.hpp)