rollback_dsu.hpp¶
支持合并、连通性查询和撤销到历史状态；常配合分治处理离线删边或时间区间事件。
Complexity: Time: O(log n) find/merge and O(1) rollback. Space: O(n + h), where h is the number of retained rollback records.
AC 记录：unionfind。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(log n) find/merge and O(1) rollback.
/// Space: O(n + h), where h is the number of retained rollback records.
#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 ra;
int va;
int rb;
int vb;
};
std::vector<int> p;
std::vector<change> his;
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);
p.assign(n, -1);
his.clear();
}
/// @brief Return the representative of x without path compression.
int leader(int x) const {
assert(0 <= x && x < int(p.size()));
while (p[x] >= 0) {
x = p[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 -p[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) {
his.push_back({-1, 0, -1, 0});
return false;
}
if (-p[a] < -p[b]) {
std::swap(a, b);
}
his.push_back({a, p[a], b, p[b]});
p[a] += p[b];
p[b] = a;
return true;
}
/// @brief Return a rollback state for use with rollback().
int snapshot() const { return int(his.size()); }
/// @brief Undo the most recent merge attempt.
void undo() {
assert(!his.empty());
change lst = his.back();
his.pop_back();
if (lst.ra == -1) {
return;
}
p[lst.ra] = lst.va;
p[lst.rb] = lst.vb;
}
/// @brief Roll back to a value previously returned by snapshot().
void rollback(int t) {
assert(0 <= t && t <= int(his.size()));
while (int(his.size()) > t) {
undo();
}
}
};
} // namespace noya
#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 + h), where h is the number of retained rollback records.
#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 ra;
int va;
int rb;
int vb;
};
std::vector<int> p;
std::vector<change> his;
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);
p.assign(n, -1);
his.clear();
}
/// @brief Return the representative of x without path compression.
int leader(int x) const {
assert(0 <= x && x < int(p.size()));
while (p[x] >= 0) {
x = p[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 -p[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) {
his.push_back({-1, 0, -1, 0});
return false;
}
if (-p[a] < -p[b]) {
std::swap(a, b);
}
his.push_back({a, p[a], b, p[b]});
p[a] += p[b];
p[b] = a;
return true;
}
/// @brief Return a rollback state for use with rollback().
int snapshot() const { return int(his.size()); }
/// @brief Undo the most recent merge attempt.
void undo() {
assert(!his.empty());
change lst = his.back();
his.pop_back();
if (lst.ra == -1) {
return;
}
p[lst.ra] = lst.va;
p[lst.rb] = lst.vb;
}
/// @brief Roll back to a value previously returned by snapshot().
void rollback(int t) {
assert(0 <= t && t <= int(his.size()));
while (int(his.size()) > t) {
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 + h), where h is the number of retained rollback records.
namespace noya {
/// @brief Union-find with O(log n) queries and O(1) rollback per merge.
struct rollback_dsu {
struct change {
int ra;
int va;
int rb;
int vb;
};
std::vector<int> p;
std::vector<change> his;
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);
p.assign(n, -1);
his.clear();
}
/// @brief Return the representative of x without path compression.
int leader(int x) const {
assert(0 <= x && x < int(p.size()));
while (p[x] >= 0) {
x = p[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 -p[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) {
his.push_back({-1, 0, -1, 0});
return false;
}
if (-p[a] < -p[b]) {
std::swap(a, b);
}
his.push_back({a, p[a], b, p[b]});
p[a] += p[b];
p[b] = a;
return true;
}
/// @brief Return a rollback state for use with rollback().
int snapshot() const { return int(his.size()); }
/// @brief Undo the most recent merge attempt.
void undo() {
assert(!his.empty());
change lst = his.back();
his.pop_back();
if (lst.ra == -1) {
return;
}
p[lst.ra] = lst.va;
p[lst.rb] = lst.vb;
}
/// @brief Roll back to a value previously returned by snapshot().
void rollback(int t) {
assert(0 <= t && t <= int(his.size()));
while (int(his.size()) > t) {
undo();
}
}
};
} // namespace noya