Rollback DSU
(ds/dsu/rollback_dsu.hpp)
- View this file on GitHub
- Last update: 2026-07-11 19:52:35+09:00
- Include:
#include "ds/dsu/rollback_dsu.hpp"
Overview
RollbackDsu maintains a partition under merges and can restore any earlier
snapshot on the current history path. It is useful for divide-and-conquer over
time, segment trees over query intervals, version trees, and offline dynamic
connectivity.
Union by size keeps each parent chain logarithmic. Path compression is intentionally omitted because it would mutate an unbounded number of entries that then need to be logged.
Every merge call appends exactly one history entry. A redundant merge appends
a no-op entry and returns false, so one call to undo() always reverses one
call to merge().
API
struct RollbackDsu {
RollbackDsu();
explicit RollbackDsu(int n);
int size() const;
bool empty() const;
int component_count() const;
int history_size() const;
void reserve_history(int count);
int leader(int vertex) const;
bool same(int first, int second) const;
int group_size(int vertex) const;
int size(int vertex) const;
bool merge(int first, int second);
bool undo();
int snapshot() const;
void rollback(int state);
std::vector<std::vector<int>> groups() const;
};
| Method | Description | Complexity |
|---|---|---|
RollbackDsu() |
Creates an empty DSU. | $O(1)$ |
RollbackDsu(n) |
Creates n singleton sets. |
$O(N)$ |
size() |
Returns the number of elements. | $O(1)$ |
empty() |
Returns whether there are no elements. | $O(1)$ |
component_count() |
Returns the current number of sets. | $O(1)$ |
history_size() |
Returns the number of recorded merge calls. | $O(1)$ |
reserve_history(count) |
Reserves history capacity. | $O(H)$ if reallocation occurs |
leader(v) |
Returns the representative containing v. |
$O(\log N)$ |
same(u, v) |
Returns whether u and v are connected. |
$O(\log N)$ |
group_size(v), size(v)
|
Returns the size of the set containing v. |
$O(\log N)$ |
merge(u, v) |
Records one operation and merges the sets if distinct; returns whether the partition changed. | $O(\log N)$ amortized for history growth |
undo() |
Reverses the most recent merge call; returns false when history is empty. |
$O(1)$ |
snapshot() |
Returns the current history position. | $O(1)$ |
rollback(state) |
Restores a previously returned snapshot on the current history path. | $O(H - state)$ |
groups() |
Materializes every current set. | $O(N \log N)$ |
Indices must lie in [0, size()). A rollback state must lie between 0 and
the current history_size(). Rolling forward to a discarded state is not
supported. Query methods are const and never change the represented state.
The DSU stores $O(N + H)$ integers, where H is the current history length.
Example
#include "ds/dsu/rollback_dsu.hpp"
#include <iostream>
int main() {
m1une::ds::RollbackDsu dsu(4);
dsu.merge(0, 1);
int checkpoint = dsu.snapshot();
dsu.merge(1, 2);
std::cout << dsu.same(0, 2) << "\n"; // 1
dsu.rollback(checkpoint);
std::cout << dsu.same(0, 2) << "\n"; // 0
std::cout << dsu.component_count() << "\n"; // 3
}
Required by
- Dynamic Connectivity
(ds/dynamic_connectivity/all.hpp)
- Offline Dynamic Connectivity
(ds/dynamic_connectivity/offline_dynamic_connectivity.hpp)
Verified with
Code
#ifndef M1UNE_ROLLBACK_DSU_HPP
#define M1UNE_ROLLBACK_DSU_HPP 1
#include <algorithm>
#include <cassert>
#include <vector>
namespace m1une {
namespace ds {
struct RollbackDsu {
private:
struct HistoryEntry {
int first;
int first_value;
int second;
int second_value;
};
int _n;
int _component_count;
std::vector<int> parent_or_size;
std::vector<HistoryEntry> history;
static int check_size(int n) {
assert(0 <= n);
return n;
}
public:
RollbackDsu() : RollbackDsu(0) {}
explicit RollbackDsu(int n)
: _n(check_size(n)), _component_count(_n), parent_or_size(_n, -1) {}
int size() const {
return _n;
}
bool empty() const {
return _n == 0;
}
int component_count() const {
return _component_count;
}
int history_size() const {
return int(history.size());
}
void reserve_history(int count) {
assert(0 <= count);
history.reserve(count);
}
int leader(int vertex) const {
assert(0 <= vertex && vertex < _n);
while (parent_or_size[vertex] >= 0) vertex = parent_or_size[vertex];
return vertex;
}
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);
}
bool merge(int first, int second) {
first = leader(first);
second = leader(second);
if (first == second) {
history.push_back(HistoryEntry{-1, 0, -1, 0});
return false;
}
if (-parent_or_size[first] < -parent_or_size[second]) {
std::swap(first, second);
}
history.push_back(HistoryEntry{
first, parent_or_size[first], second, parent_or_size[second]
});
parent_or_size[first] += parent_or_size[second];
parent_or_size[second] = first;
_component_count--;
return true;
}
bool undo() {
if (history.empty()) return false;
const HistoryEntry entry = history.back();
history.pop_back();
if (entry.first == -1) return true;
parent_or_size[entry.first] = entry.first_value;
parent_or_size[entry.second] = entry.second_value;
_component_count++;
return true;
}
int snapshot() const {
return history_size();
}
void rollback(int state) {
assert(0 <= state && state <= history_size());
while (history_size() > state) undo();
}
std::vector<std::vector<int>> groups() const {
std::vector<int> leader_buffer(_n);
std::vector<int> group_sizes(_n, 0);
for (int vertex = 0; vertex < _n; vertex++) {
leader_buffer[vertex] = leader(vertex);
group_sizes[leader_buffer[vertex]]++;
}
std::vector<std::vector<int>> result(_n);
for (int vertex = 0; vertex < _n; vertex++) {
result[vertex].reserve(group_sizes[vertex]);
}
for (int vertex = 0; vertex < _n; vertex++) {
result[leader_buffer[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_ROLLBACK_DSU_HPP#line 1 "ds/dsu/rollback_dsu.hpp"
#include <algorithm>
#include <cassert>
#include <vector>
namespace m1une {
namespace ds {
struct RollbackDsu {
private:
struct HistoryEntry {
int first;
int first_value;
int second;
int second_value;
};
int _n;
int _component_count;
std::vector<int> parent_or_size;
std::vector<HistoryEntry> history;
static int check_size(int n) {
assert(0 <= n);
return n;
}
public:
RollbackDsu() : RollbackDsu(0) {}
explicit RollbackDsu(int n)
: _n(check_size(n)), _component_count(_n), parent_or_size(_n, -1) {}
int size() const {
return _n;
}
bool empty() const {
return _n == 0;
}
int component_count() const {
return _component_count;
}
int history_size() const {
return int(history.size());
}
void reserve_history(int count) {
assert(0 <= count);
history.reserve(count);
}
int leader(int vertex) const {
assert(0 <= vertex && vertex < _n);
while (parent_or_size[vertex] >= 0) vertex = parent_or_size[vertex];
return vertex;
}
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);
}
bool merge(int first, int second) {
first = leader(first);
second = leader(second);
if (first == second) {
history.push_back(HistoryEntry{-1, 0, -1, 0});
return false;
}
if (-parent_or_size[first] < -parent_or_size[second]) {
std::swap(first, second);
}
history.push_back(HistoryEntry{
first, parent_or_size[first], second, parent_or_size[second]
});
parent_or_size[first] += parent_or_size[second];
parent_or_size[second] = first;
_component_count--;
return true;
}
bool undo() {
if (history.empty()) return false;
const HistoryEntry entry = history.back();
history.pop_back();
if (entry.first == -1) return true;
parent_or_size[entry.first] = entry.first_value;
parent_or_size[entry.second] = entry.second_value;
_component_count++;
return true;
}
int snapshot() const {
return history_size();
}
void rollback(int state) {
assert(0 <= state && state <= history_size());
while (history_size() > state) undo();
}
std::vector<std::vector<int>> groups() const {
std::vector<int> leader_buffer(_n);
std::vector<int> group_sizes(_n, 0);
for (int vertex = 0; vertex < _n; vertex++) {
leader_buffer[vertex] = leader(vertex);
group_sizes[leader_buffer[vertex]]++;
}
std::vector<std::vector<int>> result(_n);
for (int vertex = 0; vertex < _n; vertex++) {
result[vertex].reserve(group_sizes[vertex]);
}
for (int vertex = 0; vertex < _n; vertex++) {
result[leader_buffer[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