rollback_dsu.hpp¶
Union-find with O(log n) queries and O(1) rollback per merge.
Verified by unionfind.
支持合并、连通性查询和撤销到历史状态；常配合分治处理离线删边或时间区间事件。
Implementation¶
#ifndef NOYA_ROLLBACK_DSU_HPP
#define NOYA_ROLLBACK_DSU_HPP 1
/// @complexity Time: O(log n) find/merge and O(1) rollback.
/// Space: O(n + number of unrolled merges).
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
/// @brief Union-find with O(log n) queries and O(1) rollback per merge.
struct rollback_dsu {
struct change {
int first_root;
int first_value;
int second_root;
int second_value;
};
std::vector<int> parent_or_size;
std::vector<change> history;
rollback_dsu() = default;
explicit rollback_dsu(int n) { build(n); }
/// @brief Reset to n singleton components and clear rollback history.
void build(int n) {
assert(n >= 0);
parent_or_size.assign(n, -1);
history.clear();
}
/// @brief Return the representative of x without path compression.
int leader(int x) const {
assert(0 <= x && x < int(parent_or_size.size()));
while (parent_or_size[x] >= 0) {
x = parent_or_size[x];
}
return x;
}
/// @brief Return whether a and b belong to the same component.
bool same(int a, int b) const { return leader(a) == leader(b); }
/// @brief Return the size of the component containing x.
int size(int x) const { return -parent_or_size[leader(x)]; }
/// @brief Merge two components and record one rollback step.
bool merge(int a, int b) {
a = leader(a);
b = leader(b);
if (a == b) {
history.push_back({-1, 0, -1, 0});
return false;
}
if (-parent_or_size[a] < -parent_or_size[b]) {
std::swap(a, b);
}
history.push_back({a, parent_or_size[a], b, parent_or_size[b]});
parent_or_size[a] += parent_or_size[b];
parent_or_size[b] = a;
return true;
}
/// @brief Return a rollback state for use with rollback().
int snapshot() const { return int(history.size()); }
/// @brief Undo the most recent merge attempt.
void undo() {
assert(!history.empty());
change last = history.back();
history.pop_back();
if (last.first_root == -1) {
return;
}
parent_or_size[last.first_root] = last.first_value;
parent_or_size[last.second_root] = last.second_value;
}
/// @brief Roll back to a value previously returned by snapshot().
void rollback(int state) {
assert(0 <= state && state <= int(history.size()));
while (int(history.size()) > state) {
undo();
}
}
};
} // namespace noya
#endif // NOYA_ROLLBACK_DSU_HPP
#include <cassert>
#include <utility>
#include <vector>
/// @complexity Time: O(log n) find/merge and O(1) rollback.
/// Space: O(n + number of unrolled merges).
namespace noya {
/// @brief Union-find with O(log n) queries and O(1) rollback per merge.
struct rollback_dsu {
struct change {
int first_root;
int first_value;
int second_root;
int second_value;
};
std::vector<int> parent_or_size;
std::vector<change> history;
rollback_dsu() = default;
explicit rollback_dsu(int n) { build(n); }
/// @brief Reset to n singleton components and clear rollback history.
void build(int n) {
assert(n >= 0);
parent_or_size.assign(n, -1);
history.clear();
}
/// @brief Return the representative of x without path compression.
int leader(int x) const {
assert(0 <= x && x < int(parent_or_size.size()));
while (parent_or_size[x] >= 0) {
x = parent_or_size[x];
}
return x;
}
/// @brief Return whether a and b belong to the same component.
bool same(int a, int b) const { return leader(a) == leader(b); }
/// @brief Return the size of the component containing x.
int size(int x) const { return -parent_or_size[leader(x)]; }
/// @brief Merge two components and record one rollback step.
bool merge(int a, int b) {
a = leader(a);
b = leader(b);
if (a == b) {
history.push_back({-1, 0, -1, 0});
return false;
}
if (-parent_or_size[a] < -parent_or_size[b]) {
std::swap(a, b);
}
history.push_back({a, parent_or_size[a], b, parent_or_size[b]});
parent_or_size[a] += parent_or_size[b];
parent_or_size[b] = a;
return true;
}
/// @brief Return a rollback state for use with rollback().
int snapshot() const { return int(history.size()); }
/// @brief Undo the most recent merge attempt.
void undo() {
assert(!history.empty());
change last = history.back();
history.pop_back();
if (last.first_root == -1) {
return;
}
parent_or_size[last.first_root] = last.first_value;
parent_or_size[last.second_root] = last.second_value;
}
/// @brief Roll back to a value previously returned by snapshot().
void rollback(int state) {
assert(0 <= state && state <= int(history.size()));
while (int(history.size()) > state) {
undo();
}
}
};
} // namespace noya