Rollback Potentialized DSU
(ds/dsu/rollback_potentialized_dsu.hpp)

• View this file on GitHub
• Last update: 2026-08-12 17:21:09+09:00
• Include: #include "ds/dsu/rollback_potentialized_dsu.hpp"

Overview

RollbackPotentializedDsu<Group> is a weighted Union-Find with registered snapshots. It supports possibly noncommutative groups and uses union by size without path compression, so every tree has logarithmic depth.

For merge(a, b, w), the stored constraint is diff(a, b) == w, where diff(a, b) = Group::op(Group::inv(potential(a)), potential(b)). The group value type must be equality comparable so a constraint inside an existing component can be checked.

Methods

Method	Description	Complexity
RollbackPotentializedDsu()	Constructs an empty DSU.	$O(1)$
explicit RollbackPotentializedDsu(int n)	Constructs n singleton components.	$O(N)$
int size() const, bool empty() const	Returns the element count or whether it is zero.	$O(1)$
int component_count() const	Returns the current component count.	$O(1)$
int leader(int vertex) const	Returns the component representative.	$O(\log N)$
bool same(int first, int second) const	Tests connectivity.	$O(\log N)$
int group_size(int vertex) const, int size(int vertex) const	Returns the component size.	$O(\log N)$
T potential(int vertex) const	Returns the root-relative potential.	$O(\log N)$
T diff(int first, int second) const	Returns the potential difference; requires connectivity.	$O(\log N)$
int parent_or_size(int vertex) const	Returns the internal parent-or-negative-size entry.	$O(1)$
bool merge(int first, int second, const T& difference)	Adds diff(first, second) == difference; returns whether the constraints are consistent.	$O(\log N)$
int snapshot()	Registers the current state and returns its token.	$O(1)$
int snapshot_count() const	Returns the number of active snapshots.	$O(1)$
void reserve_snapshots(int count)	Reserves snapshot tokens.	$O(H)$
void rollback(int state)	Restores a current-path snapshot.	$O(M)$ for $M$ reverted successful merges
void clear_history()	Commits the current state and invalidates snapshots.	$O(H)$
std::vector<std::vector<int>> groups() const	Materializes all components.	$O(N \log N)$

Indices must lie in [0, size()). A rollback token must be active.

Snapshot semantics

Updates made before the first snapshot() retain no rollback data. A snapshot token is positive and valid only on the current path. rollback(state) restores that registered state, keeps it active, and invalidates newer snapshots. clear_history() commits the current state and invalidates every token. No per-update reversal operation is provided.

Example

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

using Add = m1une::monoid::Add<long long>;
m1une::ds::RollbackPotentializedDsu<Add> dsu(3);
dsu.merge(0, 1, 3);
int state = dsu.snapshot();
dsu.merge(1, 2, 4);
assert(dsu.diff(0, 2) == 7);
dsu.rollback(state);
assert(!dsu.same(0, 2));

Depends on

• Monoid Concept (monoid/concept.hpp)

Verified with

• verify/ds/dsu/rollback_potentialized_dsu.test.cpp
• verify/ds/rollback_counterparts.test.cpp

Code

#ifndef M1UNE_DS_DSU_ROLLBACK_POTENTIALIZED_DSU_HPP
#define M1UNE_DS_DSU_ROLLBACK_POTENTIALIZED_DSU_HPP 1

#include <algorithm>
#include <cassert>
#include <concepts>
#include <cstddef>
#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 RollbackPotentializedDsu {
    using T = typename Group::value_type;

   private:
    struct HistoryEntry {
        int first;
        int first_value;
        int second;
        int second_value;
        T second_diff;

        HistoryEntry(int first_index, int first_parent, int second_index,
                     int second_parent, T diff)
            : first(first_index),
              first_value(first_parent),
              second(second_index),
              second_value(second_parent),
              second_diff(std::move(diff)) {}
    };

    int _n;
    int _component_count;
    std::vector<int> _parent_or_size;
    std::vector<T> _diff_to_parent;
    std::vector<HistoryEntry> _history;
    std::vector<std::size_t> _checkpoints;

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

    std::pair<int, T> leader_and_potential(int vertex) const {
        assert(0 <= vertex && vertex < _n);
        T result = Group::id();
        while (_parent_or_size[vertex] >= 0) {
            result = Group::op(_diff_to_parent[vertex], result);
            vertex = _parent_or_size[vertex];
        }
        return {vertex, std::move(result)};
    }

   public:
    RollbackPotentializedDsu() : RollbackPotentializedDsu(0) {}

    explicit RollbackPotentializedDsu(int n)
        : _n(check_size(n)),
          _component_count(_n),
          _parent_or_size(_n, -1),
          _diff_to_parent(_n, Group::id()) {}

    int size() const { return _n; }
    bool empty() const { return _n == 0; }
    int component_count() const { return _component_count; }
    int snapshot_count() const { return int(_checkpoints.size()); }

    void reserve_snapshots(int count) {
        assert(0 <= count);
        _checkpoints.reserve(count);
    }

    int leader(int vertex) const {
        return leader_and_potential(vertex).first;
    }

    bool same(int first, int second) const {
        return leader(first) == leader(second);
    }

    int group_size(int vertex) const {
        return -_parent_or_size[leader(vertex)];
    }

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

    T potential(int vertex) const {
        return leader_and_potential(vertex).second;
    }

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

    int parent_or_size(int vertex) const {
        assert(0 <= vertex && vertex < _n);
        return _parent_or_size[vertex];
    }

    bool merge(int first, int second, const T& difference) {
        auto [first_root, first_potential] = leader_and_potential(first);
        auto [second_root, second_potential] = leader_and_potential(second);
        if (first_root == second_root) {
            return Group::op(Group::inv(first_potential), second_potential) == difference;
        }

        T second_from_first = Group::op(
            Group::op(first_potential, difference),
            Group::inv(second_potential)
        );
        if (-_parent_or_size[first_root] < -_parent_or_size[second_root]) {
            std::swap(first_root, second_root);
            second_from_first = Group::inv(second_from_first);
        }

        if (!_checkpoints.empty()) {
            _history.emplace_back(
                first_root, _parent_or_size[first_root], second_root,
                _parent_or_size[second_root], _diff_to_parent[second_root]
            );
        }
        _parent_or_size[first_root] += _parent_or_size[second_root];
        _parent_or_size[second_root] = first_root;
        _diff_to_parent[second_root] = std::move(second_from_first);
        --_component_count;
        return true;
    }

   private:
    void restore_one() {
        HistoryEntry entry = std::move(_history.back());
        _history.pop_back();
        _parent_or_size[entry.first] = entry.first_value;
        _parent_or_size[entry.second] = entry.second_value;
        _diff_to_parent[entry.second] = std::move(entry.second_diff);
        ++_component_count;
    }

   public:
    int snapshot() { _checkpoints.push_back(_history.size()); return int(_checkpoints.size()); }

    void rollback(int state) {
        assert(1 <= state && state <= snapshot_count());
        while (_history.size() > _checkpoints[state - 1]) restore_one();
        _checkpoints.resize(state);
    }

    void clear_history() { _history.clear(); _checkpoints.clear(); }

    std::vector<std::vector<int>> groups() const {
        std::vector<int> leaders(_n);
        std::vector<int> sizes(_n);
        for (int vertex = 0; vertex < _n; ++vertex) {
            leaders[vertex] = leader(vertex);
            ++sizes[leaders[vertex]];
        }
        std::vector<std::vector<int>> result(_n);
        for (int vertex = 0; vertex < _n; ++vertex) {
            result[vertex].reserve(sizes[vertex]);
        }
        for (int vertex = 0; vertex < _n; ++vertex) {
            result[leaders[vertex]].push_back(vertex);
        }
        result.erase(
            std::remove_if(
                result.begin(), result.end(),
                [](const std::vector<int>& group) { return group.empty(); }
            ),
            result.end()
        );
        return result;
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DS_DSU_ROLLBACK_POTENTIALIZED_DSU_HPP

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



#include <algorithm>
#include <cassert>
#include <concepts>
#include <cstddef>
#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/rollback_potentialized_dsu.hpp"

namespace m1une {
namespace ds {

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

   private:
    struct HistoryEntry {
        int first;
        int first_value;
        int second;
        int second_value;
        T second_diff;

        HistoryEntry(int first_index, int first_parent, int second_index,
                     int second_parent, T diff)
            : first(first_index),
              first_value(first_parent),
              second(second_index),
              second_value(second_parent),
              second_diff(std::move(diff)) {}
    };

    int _n;
    int _component_count;
    std::vector<int> _parent_or_size;
    std::vector<T> _diff_to_parent;
    std::vector<HistoryEntry> _history;
    std::vector<std::size_t> _checkpoints;

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

    std::pair<int, T> leader_and_potential(int vertex) const {
        assert(0 <= vertex && vertex < _n);
        T result = Group::id();
        while (_parent_or_size[vertex] >= 0) {
            result = Group::op(_diff_to_parent[vertex], result);
            vertex = _parent_or_size[vertex];
        }
        return {vertex, std::move(result)};
    }

   public:
    RollbackPotentializedDsu() : RollbackPotentializedDsu(0) {}

    explicit RollbackPotentializedDsu(int n)
        : _n(check_size(n)),
          _component_count(_n),
          _parent_or_size(_n, -1),
          _diff_to_parent(_n, Group::id()) {}

    int size() const { return _n; }
    bool empty() const { return _n == 0; }
    int component_count() const { return _component_count; }
    int snapshot_count() const { return int(_checkpoints.size()); }

    void reserve_snapshots(int count) {
        assert(0 <= count);
        _checkpoints.reserve(count);
    }

    int leader(int vertex) const {
        return leader_and_potential(vertex).first;
    }

    bool same(int first, int second) const {
        return leader(first) == leader(second);
    }

    int group_size(int vertex) const {
        return -_parent_or_size[leader(vertex)];
    }

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

    T potential(int vertex) const {
        return leader_and_potential(vertex).second;
    }

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

    int parent_or_size(int vertex) const {
        assert(0 <= vertex && vertex < _n);
        return _parent_or_size[vertex];
    }

    bool merge(int first, int second, const T& difference) {
        auto [first_root, first_potential] = leader_and_potential(first);
        auto [second_root, second_potential] = leader_and_potential(second);
        if (first_root == second_root) {
            return Group::op(Group::inv(first_potential), second_potential) == difference;
        }

        T second_from_first = Group::op(
            Group::op(first_potential, difference),
            Group::inv(second_potential)
        );
        if (-_parent_or_size[first_root] < -_parent_or_size[second_root]) {
            std::swap(first_root, second_root);
            second_from_first = Group::inv(second_from_first);
        }

        if (!_checkpoints.empty()) {
            _history.emplace_back(
                first_root, _parent_or_size[first_root], second_root,
                _parent_or_size[second_root], _diff_to_parent[second_root]
            );
        }
        _parent_or_size[first_root] += _parent_or_size[second_root];
        _parent_or_size[second_root] = first_root;
        _diff_to_parent[second_root] = std::move(second_from_first);
        --_component_count;
        return true;
    }

   private:
    void restore_one() {
        HistoryEntry entry = std::move(_history.back());
        _history.pop_back();
        _parent_or_size[entry.first] = entry.first_value;
        _parent_or_size[entry.second] = entry.second_value;
        _diff_to_parent[entry.second] = std::move(entry.second_diff);
        ++_component_count;
    }

   public:
    int snapshot() { _checkpoints.push_back(_history.size()); return int(_checkpoints.size()); }

    void rollback(int state) {
        assert(1 <= state && state <= snapshot_count());
        while (_history.size() > _checkpoints[state - 1]) restore_one();
        _checkpoints.resize(state);
    }

    void clear_history() { _history.clear(); _checkpoints.clear(); }

    std::vector<std::vector<int>> groups() const {
        std::vector<int> leaders(_n);
        std::vector<int> sizes(_n);
        for (int vertex = 0; vertex < _n; ++vertex) {
            leaders[vertex] = leader(vertex);
            ++sizes[leaders[vertex]];
        }
        std::vector<std::vector<int>> result(_n);
        for (int vertex = 0; vertex < _n; ++vertex) {
            result[vertex].reserve(sizes[vertex]);
        }
        for (int vertex = 0; vertex < _n; ++vertex) {
            result[leaders[vertex]].push_back(vertex);
        }
        result.erase(
            std::remove_if(
                result.begin(), result.end(),
                [](const std::vector<int>& group) { return group.empty(); }
            ),
            result.end()
        );
        return result;
    }
};

}  // namespace ds
}  // namespace m1une

Back to top page