offline_dynamic_connectivity.hpp¶
离线处理无向图的加边、删边和连通性询问；把边的生存区间分治后用回滚并查集求解。
Complexity: Time: O((Q log Q) log V) with rollback DSU. Space: O(Q log Q + V).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O((Q log Q) log V) with rollback DSU.
/// Space: O(Q log Q + V).
#include "noya/rollback_dsu.hpp"
#include <algorithm>
#include <cassert>
#include <map>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline fully dynamic connectivity with add, remove, and same
/// queries.
struct offline_dynamic_connectivity {
enum class event_type { add, remove, query };
struct event {
event_type ty;
int a;
int b;
int qid = -1;
};
int nv = 0;
int qn = 0;
std::vector<event> ev;
offline_dynamic_connectivity() = default;
explicit offline_dynamic_connectivity(int n) : nv(n) { assert(n >= 0); }
/// @brief Record the insertion of one copy of an undirected edge.
void add_edge(int a, int b) {
check_vertex(a);
check_vertex(b);
normalize(a, b);
ev.push_back({event_type::add, a, b});
}
/// @brief Record the removal of the most recently added active copy.
void remove_edge(int a, int b) {
check_vertex(a);
check_vertex(b);
normalize(a, b);
ev.push_back({event_type::remove, a, b});
}
/// @brief Record a connectivity query and return its answer index.
int add_query(int a, int b) {
check_vertex(a);
check_vertex(b);
int id = qn++;
ev.push_back({event_type::query, a, b, id});
return id;
}
/// @brief Solve all recorded queries in O((m + q) log m log n).
std::vector<bool> solve() const {
int nt = int(ev.size());
std::vector<std::vector<std::pair<int, int>>> seg(std::max(1, 4 * nt));
std::map<std::pair<int, int>, std::vector<int>> act;
auto ai = [&](auto &self, int nd, int l, int r, int ql, int qr,
std::pair<int, int> e) -> void {
if (qr <= l || r <= ql) {
return;
}
if (ql <= l && r <= qr) {
seg[nd].push_back(e);
return;
}
int mid = (l + r) / 2;
self(self, nd * 2, l, mid, ql, qr, e);
self(self, nd * 2 + 1, mid, r, ql, qr, e);
};
for (int tm = 0; tm < nt; tm++) {
const event &cur = ev[tm];
std::pair<int, int> e = {cur.a, cur.b};
if (cur.ty == event_type::add) {
act[e].push_back(tm);
} else if (cur.ty == event_type::remove) {
auto it = act.find(e);
assert(it != act.end() && !it->second.empty());
if (it == act.end() || it->second.empty()) {
continue;
}
int s = it->second.back();
it->second.pop_back();
ai(ai, 1, 0, nt, s, tm, e);
}
}
for (const auto &[e, sta] : act) {
for (int s : sta) {
ai(ai, 1, 0, nt, s, nt, e);
}
}
std::vector<bool> ans(qn);
rollback_dsu dsu(nv);
auto dfs = [&](auto &self, int nd, int l, int r) -> void {
int st = dsu.snapshot();
for (auto [a, b] : seg[nd]) {
dsu.merge(a, b);
}
if (r - l == 1) {
const event &cur = ev[l];
if (cur.ty == event_type::query) {
ans[cur.qid] = dsu.same(cur.a, cur.b);
}
} else {
int mid = (l + r) / 2;
self(self, nd * 2, l, mid);
self(self, nd * 2 + 1, mid, r);
}
dsu.rollback(st);
};
if (nt > 0) {
dfs(dfs, 1, 0, nt);
}
return ans;
}
private:
void check_vertex(int u) const { assert(0 <= u && u < nv); }
static void normalize(int &a, int &b) {
if (a > b) {
std::swap(a, b);
}
}
};
} // namespace noya
#ifndef NOYA_OFFLINE_DYNAMIC_CONNECTIVITY_HPP
#define NOYA_OFFLINE_DYNAMIC_CONNECTIVITY_HPP 1
/// @complexity Time: O((Q log Q) log V) with rollback DSU.
/// Space: O(Q log Q + V).
#include "noya/rollback_dsu.hpp"
#include <algorithm>
#include <cassert>
#include <map>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline fully dynamic connectivity with add, remove, and same
/// queries.
struct offline_dynamic_connectivity {
enum class event_type { add, remove, query };
struct event {
event_type ty;
int a;
int b;
int qid = -1;
};
int nv = 0;
int qn = 0;
std::vector<event> ev;
offline_dynamic_connectivity() = default;
explicit offline_dynamic_connectivity(int n) : nv(n) { assert(n >= 0); }
/// @brief Record the insertion of one copy of an undirected edge.
void add_edge(int a, int b) {
check_vertex(a);
check_vertex(b);
normalize(a, b);
ev.push_back({event_type::add, a, b});
}
/// @brief Record the removal of the most recently added active copy.
void remove_edge(int a, int b) {
check_vertex(a);
check_vertex(b);
normalize(a, b);
ev.push_back({event_type::remove, a, b});
}
/// @brief Record a connectivity query and return its answer index.
int add_query(int a, int b) {
check_vertex(a);
check_vertex(b);
int id = qn++;
ev.push_back({event_type::query, a, b, id});
return id;
}
/// @brief Solve all recorded queries in O((m + q) log m log n).
std::vector<bool> solve() const {
int nt = int(ev.size());
std::vector<std::vector<std::pair<int, int>>> seg(std::max(1, 4 * nt));
std::map<std::pair<int, int>, std::vector<int>> act;
auto ai = [&](auto &self, int nd, int l, int r, int ql, int qr,
std::pair<int, int> e) -> void {
if (qr <= l || r <= ql) {
return;
}
if (ql <= l && r <= qr) {
seg[nd].push_back(e);
return;
}
int mid = (l + r) / 2;
self(self, nd * 2, l, mid, ql, qr, e);
self(self, nd * 2 + 1, mid, r, ql, qr, e);
};
for (int tm = 0; tm < nt; tm++) {
const event &cur = ev[tm];
std::pair<int, int> e = {cur.a, cur.b};
if (cur.ty == event_type::add) {
act[e].push_back(tm);
} else if (cur.ty == event_type::remove) {
auto it = act.find(e);
assert(it != act.end() && !it->second.empty());
if (it == act.end() || it->second.empty()) {
continue;
}
int s = it->second.back();
it->second.pop_back();
ai(ai, 1, 0, nt, s, tm, e);
}
}
for (const auto &[e, sta] : act) {
for (int s : sta) {
ai(ai, 1, 0, nt, s, nt, e);
}
}
std::vector<bool> ans(qn);
rollback_dsu dsu(nv);
auto dfs = [&](auto &self, int nd, int l, int r) -> void {
int st = dsu.snapshot();
for (auto [a, b] : seg[nd]) {
dsu.merge(a, b);
}
if (r - l == 1) {
const event &cur = ev[l];
if (cur.ty == event_type::query) {
ans[cur.qid] = dsu.same(cur.a, cur.b);
}
} else {
int mid = (l + r) / 2;
self(self, nd * 2, l, mid);
self(self, nd * 2 + 1, mid, r);
}
dsu.rollback(st);
};
if (nt > 0) {
dfs(dfs, 1, 0, nt);
}
return ans;
}
private:
void check_vertex(int u) const { assert(0 <= u && u < nv); }
static void normalize(int &a, int &b) {
if (a > b) {
std::swap(a, b);
}
}
};
} // namespace noya
#endif // NOYA_OFFLINE_DYNAMIC_CONNECTIVITY_HPP
#include <algorithm>
#include <cassert>
#include <map>
#include <utility>
#include <vector>
/// @complexity Time: O((Q log Q) log V) with rollback DSU.
/// Space: O(Q log Q + V).
/// @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
namespace noya {
/// @brief Offline fully dynamic connectivity with add, remove, and same
/// queries.
struct offline_dynamic_connectivity {
enum class event_type { add, remove, query };
struct event {
event_type ty;
int a;
int b;
int qid = -1;
};
int nv = 0;
int qn = 0;
std::vector<event> ev;
offline_dynamic_connectivity() = default;
explicit offline_dynamic_connectivity(int n) : nv(n) { assert(n >= 0); }
/// @brief Record the insertion of one copy of an undirected edge.
void add_edge(int a, int b) {
check_vertex(a);
check_vertex(b);
normalize(a, b);
ev.push_back({event_type::add, a, b});
}
/// @brief Record the removal of the most recently added active copy.
void remove_edge(int a, int b) {
check_vertex(a);
check_vertex(b);
normalize(a, b);
ev.push_back({event_type::remove, a, b});
}
/// @brief Record a connectivity query and return its answer index.
int add_query(int a, int b) {
check_vertex(a);
check_vertex(b);
int id = qn++;
ev.push_back({event_type::query, a, b, id});
return id;
}
/// @brief Solve all recorded queries in O((m + q) log m log n).
std::vector<bool> solve() const {
int nt = int(ev.size());
std::vector<std::vector<std::pair<int, int>>> seg(std::max(1, 4 * nt));
std::map<std::pair<int, int>, std::vector<int>> act;
auto ai = [&](auto &self, int nd, int l, int r, int ql, int qr,
std::pair<int, int> e) -> void {
if (qr <= l || r <= ql) {
return;
}
if (ql <= l && r <= qr) {
seg[nd].push_back(e);
return;
}
int mid = (l + r) / 2;
self(self, nd * 2, l, mid, ql, qr, e);
self(self, nd * 2 + 1, mid, r, ql, qr, e);
};
for (int tm = 0; tm < nt; tm++) {
const event &cur = ev[tm];
std::pair<int, int> e = {cur.a, cur.b};
if (cur.ty == event_type::add) {
act[e].push_back(tm);
} else if (cur.ty == event_type::remove) {
auto it = act.find(e);
assert(it != act.end() && !it->second.empty());
if (it == act.end() || it->second.empty()) {
continue;
}
int s = it->second.back();
it->second.pop_back();
ai(ai, 1, 0, nt, s, tm, e);
}
}
for (const auto &[e, sta] : act) {
for (int s : sta) {
ai(ai, 1, 0, nt, s, nt, e);
}
}
std::vector<bool> ans(qn);
rollback_dsu dsu(nv);
auto dfs = [&](auto &self, int nd, int l, int r) -> void {
int st = dsu.snapshot();
for (auto [a, b] : seg[nd]) {
dsu.merge(a, b);
}
if (r - l == 1) {
const event &cur = ev[l];
if (cur.ty == event_type::query) {
ans[cur.qid] = dsu.same(cur.a, cur.b);
}
} else {
int mid = (l + r) / 2;
self(self, nd * 2, l, mid);
self(self, nd * 2 + 1, mid, r);
}
dsu.rollback(st);
};
if (nt > 0) {
dfs(dfs, 1, 0, nt);
}
return ans;
}
private:
void check_vertex(int u) const { assert(0 <= u && u < nv); }
static void normalize(int &a, int &b) {
if (a > b) {
std::swap(a, b);
}
}
};
} // namespace noya