offline_dynamic_connectivity.hpp¶
离线无向图加删边与连通查询；压缩查询时间、合并平行边区间，用回滚并查集处理，查询看不到有效边时直接回答。
Complexity: Time: \(O(V + Q \log (Q + 1) + (E \log (K + 1) + K) \log (V + 1))\). Space: \(O(V + Q + E \log (K + 1))\); \(K\) queries, \(E\) coalesced edge lifetimes, \(Q\) events.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V+Q log(Q+1)+(E log(K+1)+K) log(V+1)).
/// Space: O(V+Q+E log(K+1)); K queries, E coalesced edge lifetimes, Q events.
#include "noya/ds/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. Parallel copies share a lifetime until their count returns to zero;
/// only query times become leaves. The recursive traversal rolls back merges.
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 queries without changing the recorded event stream.
std::vector<bool> solve() const {
if (qn == 0) return {};
std::size_t base = 1;
while (base < std::size_t(qn)) base *= 2;
std::vector<std::vector<int>> seg;
auto insert = [&](int begin, int end, int id) {
if (begin == end) return;
if (seg.empty()) seg.resize(2 * base);
for (std::size_t l = base + begin, r = base + end; l < r; l /= 2, r /= 2) {
if (l & 1) seg[l++].push_back(id);
if (r & 1) seg[--r].push_back(id);
}
};
struct active_edge { int count, start, id; };
std::map<std::pair<int, int>, active_edge> active;
std::vector<int> queries;
queries.reserve(qn);
for (int i = 0; i < int(ev.size()); ++i) {
const auto &cur = ev[i];
int time = int(queries.size());
auto edge = std::pair{cur.a, cur.b};
if (cur.ty == event_type::add) {
auto it = active.try_emplace(active.end(), edge, active_edge{0, time, i});
++it->second.count;
} else if (cur.ty == event_type::remove) {
auto it = active.find(edge);
assert(it != active.end());
if (it == active.end()) continue;
if (--it->second.count == 0) {
if (cur.a != cur.b) insert(it->second.start, time, i);
active.erase(it);
}
} else {
queries.push_back(i);
}
}
for (const auto &[edge, state] : active)
if (edge.first != edge.second) insert(state.start, qn, state.id);
active.clear();
std::vector<bool> ans(qn);
if (seg.empty()) {
for (int id : queries) ans[ev[id].qid] = ev[id].a == ev[id].b;
return ans;
}
rollback_dsu dsu(nv);
auto dfs = [&](auto &self, std::size_t nd, std::size_t l, std::size_t r) -> void {
if (l >= std::size_t(qn)) return;
int state = dsu.snapshot();
for (int id : seg[nd]) {
int a = dsu.leader(ev[id].a), b = dsu.leader(ev[id].b);
if (a != b) dsu.merge(a, b);
}
if (r - l == 1) {
const auto &cur = ev[queries[l]];
ans[cur.qid] = cur.a == cur.b || dsu.same(cur.a, cur.b);
} else {
auto mid = (l + r) / 2;
self(self, nd * 2, l, mid);
self(self, nd * 2 + 1, mid, r);
}
dsu.rollback(state);
};
dfs(dfs, 1, 0, base);
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
// NOYA_OFFLINE_DYNAMIC_CONNECTIVITY_HPP
#ifndef NOYA_OFFLINE_DYNAMIC_CONNECTIVITY_HPP
#define NOYA_OFFLINE_DYNAMIC_CONNECTIVITY_HPP 1
/// @complexity Time: O(V+Q log(Q+1)+(E log(K+1)+K) log(V+1)).
/// Space: O(V+Q+E log(K+1)); K queries, E coalesced edge lifetimes, Q events.
#include "noya/ds/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. Parallel copies share a lifetime until their count returns to zero;
/// only query times become leaves. The recursive traversal rolls back merges.
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 queries without changing the recorded event stream.
std::vector<bool> solve() const {
if (qn == 0) return {};
std::size_t base = 1;
while (base < std::size_t(qn)) base *= 2;
std::vector<std::vector<int>> seg;
auto insert = [&](int begin, int end, int id) {
if (begin == end) return;
if (seg.empty()) seg.resize(2 * base);
for (std::size_t l = base + begin, r = base + end; l < r; l /= 2, r /= 2) {
if (l & 1) seg[l++].push_back(id);
if (r & 1) seg[--r].push_back(id);
}
};
struct active_edge { int count, start, id; };
std::map<std::pair<int, int>, active_edge> active;
std::vector<int> queries;
queries.reserve(qn);
for (int i = 0; i < int(ev.size()); ++i) {
const auto &cur = ev[i];
int time = int(queries.size());
auto edge = std::pair{cur.a, cur.b};
if (cur.ty == event_type::add) {
auto it = active.try_emplace(active.end(), edge, active_edge{0, time, i});
++it->second.count;
} else if (cur.ty == event_type::remove) {
auto it = active.find(edge);
assert(it != active.end());
if (it == active.end()) continue;
if (--it->second.count == 0) {
if (cur.a != cur.b) insert(it->second.start, time, i);
active.erase(it);
}
} else {
queries.push_back(i);
}
}
for (const auto &[edge, state] : active)
if (edge.first != edge.second) insert(state.start, qn, state.id);
active.clear();
std::vector<bool> ans(qn);
if (seg.empty()) {
for (int id : queries) ans[ev[id].qid] = ev[id].a == ev[id].b;
return ans;
}
rollback_dsu dsu(nv);
auto dfs = [&](auto &self, std::size_t nd, std::size_t l, std::size_t r) -> void {
if (l >= std::size_t(qn)) return;
int state = dsu.snapshot();
for (int id : seg[nd]) {
int a = dsu.leader(ev[id].a), b = dsu.leader(ev[id].b);
if (a != b) dsu.merge(a, b);
}
if (r - l == 1) {
const auto &cur = ev[queries[l]];
ans[cur.qid] = cur.a == cur.b || dsu.same(cur.a, cur.b);
} else {
auto mid = (l + r) / 2;
self(self, nd * 2, l, mid);
self(self, nd * 2 + 1, mid, r);
}
dsu.rollback(state);
};
dfs(dfs, 1, 0, base);
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
/// @complexity Time: O(V+Q log(Q+1)+(E log(K+1)+K) log(V+1)).
/// Space: O(V+Q+E log(K+1)); K queries, E coalesced edge lifetimes, Q events.
/// @complexity Time: O(n) build, O(log n) find/merge, O(1) undo,
/// and O(k) rollback of k merge attempts. History appends are amortized.
/// 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) {
if (a == b) {
assert(0 <= a && a < int(p.size()));
his.push_back({-1, 0, -1, 0});
return false;
}
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
#include <algorithm>
#include <cassert>
#include <map>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline fully dynamic connectivity with add, remove, and same
/// queries. Parallel copies share a lifetime until their count returns to zero;
/// only query times become leaves. The recursive traversal rolls back merges.
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 queries without changing the recorded event stream.
std::vector<bool> solve() const {
if (qn == 0) return {};
std::size_t base = 1;
while (base < std::size_t(qn)) base *= 2;
std::vector<std::vector<int>> seg;
auto insert = [&](int begin, int end, int id) {
if (begin == end) return;
if (seg.empty()) seg.resize(2 * base);
for (std::size_t l = base + begin, r = base + end; l < r; l /= 2, r /= 2) {
if (l & 1) seg[l++].push_back(id);
if (r & 1) seg[--r].push_back(id);
}
};
struct active_edge { int count, start, id; };
std::map<std::pair<int, int>, active_edge> active;
std::vector<int> queries;
queries.reserve(qn);
for (int i = 0; i < int(ev.size()); ++i) {
const auto &cur = ev[i];
int time = int(queries.size());
auto edge = std::pair{cur.a, cur.b};
if (cur.ty == event_type::add) {
auto it = active.try_emplace(active.end(), edge, active_edge{0, time, i});
++it->second.count;
} else if (cur.ty == event_type::remove) {
auto it = active.find(edge);
assert(it != active.end());
if (it == active.end()) continue;
if (--it->second.count == 0) {
if (cur.a != cur.b) insert(it->second.start, time, i);
active.erase(it);
}
} else {
queries.push_back(i);
}
}
for (const auto &[edge, state] : active)
if (edge.first != edge.second) insert(state.start, qn, state.id);
active.clear();
std::vector<bool> ans(qn);
if (seg.empty()) {
for (int id : queries) ans[ev[id].qid] = ev[id].a == ev[id].b;
return ans;
}
rollback_dsu dsu(nv);
auto dfs = [&](auto &self, std::size_t nd, std::size_t l, std::size_t r) -> void {
if (l >= std::size_t(qn)) return;
int state = dsu.snapshot();
for (int id : seg[nd]) {
int a = dsu.leader(ev[id].a), b = dsu.leader(ev[id].b);
if (a != b) dsu.merge(a, b);
}
if (r - l == 1) {
const auto &cur = ev[queries[l]];
ans[cur.qid] = cur.a == cur.b || dsu.same(cur.a, cur.b);
} else {
auto mid = (l + r) / 2;
self(self, nd * 2, l, mid);
self(self, nd * 2 + 1, mid, r);
}
dsu.rollback(state);
};
dfs(dfs, 1, 0, base);
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
// NOYA_OFFLINE_DYNAMIC_CONNECTIVITY_HPP