DSU with Monoid
(ds/dsu/dsu_monoid.hpp)

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

Overview

DsuMonoid is a Disjoint Set Union that stores one monoid aggregate for each connected component. Each singleton starts with its own value, and merge(a, b) combines the aggregate of a’s component with the aggregate of b’s component.

The structure uses path compression and union by size, so DSU operations are near constant time. The aggregate order is independent of the root chosen by union by size: for noncommutative monoids, merge(a, b) stores Monoid::op(prod(a), prod(b)).

Template Parameters

Monoid: A type satisfying m1une::monoid::IsMonoid.

The monoid must provide:

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

Construction

DsuMonoid(): creates an empty DSU.
DsuMonoid(int n): creates n singleton sets initialized with Monoid::id().
DsuMonoid(int n, const T& value): creates n singleton sets initialized with value.
DsuMonoid(const std::vector<T>& v): creates singleton sets from monoid values.
DsuMonoid(std::vector<T>&& v): creates singleton sets from moved monoid values.
DsuMonoid(const std::vector<U>& v): builds from another value type when Monoid::make(value), Monoid::make(value, index), or static_cast<T>(value) is available.
DsuMonoid(std::initializer_list<T> init): creates singleton sets from an initializer list.

Methods

Method	Description	Complexity
`int size() const`	Returns the number of elements.	$O(1)$
`bool empty() const`	Returns whether the DSU has no elements.	$O(1)$
`int merge(int a, int b)`	Merges the sets containing `a` and `b`; returns the leader of the merged set.	Amortized $O(\alpha(N))$
`bool same(int a, int b)`, `bool same(int a, int b) const`	Returns whether `a` and `b` are in the same set.	Amortized $O(\alpha(N))$
`int leader(int a)`, `int leader(int a) const`	Returns the representative of the set containing `a`.	Amortized $O(\alpha(N))$
`int group_size(int a)`, `int group_size(int a) const`, `int size(int a)`, `int size(int a) const`	Returns the size of the set containing `a`.	Amortized $O(\alpha(N))$
`T prod(int a)`, `T prod(int a) const`, `T get(int a)`, `T get(int a) const`	Returns the aggregate of the set containing `a`.	Amortized $O(\alpha(N))$
`void set(int a, T value)`	Replaces the aggregate of the set containing `a`.	Amortized $O(\alpha(N))$
`std::vector<std::vector<int>> groups()`, `std::vector<std::vector<int>> groups() const`	Returns all sets as vectors of element indices.	$O(N \alpha(N))$

Example

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

#include <iostream>
#include <vector>

int main() {
    using Sum = m1une::monoid::Add<long long>;
    m1une::ds::DsuMonoid<Sum> dsu(std::vector<long long>{1, 2, 3, 4, 5});

    dsu.merge(0, 1);
    dsu.merge(2, 3);
    dsu.merge(1, 2);

    std::cout << dsu.prod(0) << "\n";  // 10
    std::cout << dsu.size(0) << "\n";  // 4
    std::cout << dsu.prod(4) << "\n";  // 5
}

Depends on

Monoid Concept (monoid/concept.hpp)

Verified with

verify/ds/dsu/dsu_monoid.test.cpp

Code

#ifndef M1UNE_DSU_MONOID_HPP
#define M1UNE_DSU_MONOID_HPP 1

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

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

namespace m1une {
namespace ds {

template <m1une::monoid::IsMonoid Monoid>
struct DsuMonoid {
    using T = typename Monoid::value_type;

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

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

    template <typename U>
    static T make_value(const U& value, int index) {
        if constexpr (requires(U x) { Monoid::make(x); }) {
            return Monoid::make(value);
        } else if constexpr (requires(U x, int i) { Monoid::make(x, i); }) {
            return Monoid::make(value, index);
        } else {
            return static_cast<T>(value);
        }
    }

   public:
    DsuMonoid() : DsuMonoid(0) {}

    explicit DsuMonoid(int n) : DsuMonoid(n, Monoid::id()) {}

    DsuMonoid(int n, const T& value) : _n(check_size(n)), parent_or_size(_n, -1), _prod(_n, value) {}

    explicit DsuMonoid(const std::vector<T>& v) : _n(int(v.size())), parent_or_size(_n, -1), _prod(v) {}

    explicit DsuMonoid(std::vector<T>&& v) : _n(int(v.size())), parent_or_size(_n, -1), _prod(std::move(v)) {}

    template <typename U>
    requires (!std::same_as<U, T>) && (
        requires(U x) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    explicit DsuMonoid(const std::vector<U>& v) : _n(int(v.size())), parent_or_size(_n, -1), _prod(_n, Monoid::id()) {
        for (int i = 0; i < _n; i++) _prod[i] = make_value(v[i], i);
    }

    DsuMonoid(std::initializer_list<T> init) : DsuMonoid(std::vector<T>(init)) {}

    int size() const {
        return _n;
    }

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

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        T merged = Monoid::op(_prod[x], _prod[y]);
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        _prod[x] = std::move(merged);
        return x;
    }

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

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

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

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

    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 prod(int a) {
        return _prod[leader(a)];
    }

    T prod(int a) const {
        return _prod[leader(a)];
    }

    T get(int a) {
        return prod(a);
    }

    T get(int a) const {
        return prod(a);
    }

    void set(int a, T value) {
        _prod[leader(a)] = std::move(value);
    }

    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_DSU_MONOID_HPP

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



#include <algorithm>
#include <cassert>
#include <concepts>
#include <initializer_list>
#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 12 "ds/dsu/dsu_monoid.hpp"

namespace m1une {
namespace ds {

template <m1une::monoid::IsMonoid Monoid>
struct DsuMonoid {
    using T = typename Monoid::value_type;

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

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

    template <typename U>
    static T make_value(const U& value, int index) {
        if constexpr (requires(U x) { Monoid::make(x); }) {
            return Monoid::make(value);
        } else if constexpr (requires(U x, int i) { Monoid::make(x, i); }) {
            return Monoid::make(value, index);
        } else {
            return static_cast<T>(value);
        }
    }

   public:
    DsuMonoid() : DsuMonoid(0) {}

    explicit DsuMonoid(int n) : DsuMonoid(n, Monoid::id()) {}

    DsuMonoid(int n, const T& value) : _n(check_size(n)), parent_or_size(_n, -1), _prod(_n, value) {}

    explicit DsuMonoid(const std::vector<T>& v) : _n(int(v.size())), parent_or_size(_n, -1), _prod(v) {}

    explicit DsuMonoid(std::vector<T>&& v) : _n(int(v.size())), parent_or_size(_n, -1), _prod(std::move(v)) {}

    template <typename U>
    requires (!std::same_as<U, T>) && (
        requires(U x) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    explicit DsuMonoid(const std::vector<U>& v) : _n(int(v.size())), parent_or_size(_n, -1), _prod(_n, Monoid::id()) {
        for (int i = 0; i < _n; i++) _prod[i] = make_value(v[i], i);
    }

    DsuMonoid(std::initializer_list<T> init) : DsuMonoid(std::vector<T>(init)) {}

    int size() const {
        return _n;
    }

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

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        T merged = Monoid::op(_prod[x], _prod[y]);
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        _prod[x] = std::move(merged);
        return x;
    }

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

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

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

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

    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 prod(int a) {
        return _prod[leader(a)];
    }

    T prod(int a) const {
        return _prod[leader(a)];
    }

    T get(int a) {
        return prod(a);
    }

    T get(int a) const {
        return prod(a);
    }

    void set(int a, T value) {
        _prod[leader(a)] = std::move(value);
    }

    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

DSU with Monoid
(ds/dsu/dsu_monoid.hpp)

Overview

Template Parameters

Construction

Methods

Example

Depends on

Verified with

Code

DSU with Monoid (ds/dsu/dsu_monoid.hpp)

Overview

Template Parameters

Construction

Methods

Example

Depends on

Verified with

Code

DSU with Monoid
(ds/dsu/dsu_monoid.hpp)