offline_dynamic_connectivity.hpp¶
Offline fully dynamic connectivity with add, remove, and same queries.
离线处理无向图的加边、删边和连通性询问；把边的生存区间分治后用回滚并查集求解。
Implementation¶
#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 type;
int first;
int second;
int query_id = -1;
};
int vertex_count = 0;
int query_count = 0;
std::vector<event> events;
offline_dynamic_connectivity() = default;
explicit offline_dynamic_connectivity(int n) : vertex_count(n) {
assert(n >= 0);
}
/// @brief Record the insertion of one copy of an undirected edge.
void add_edge(int first, int second) {
check_vertex(first);
check_vertex(second);
normalize(first, second);
events.push_back({event_type::add, first, second});
}
/// @brief Record the removal of the most recently added active copy.
void remove_edge(int first, int second) {
check_vertex(first);
check_vertex(second);
normalize(first, second);
events.push_back({event_type::remove, first, second});
}
/// @brief Record a connectivity query and return its answer index.
int add_query(int first, int second) {
check_vertex(first);
check_vertex(second);
int id = query_count++;
events.push_back({event_type::query, first, second, id});
return id;
}
/// @brief Solve all recorded queries in O((m + q) log m log n).
std::vector<bool> solve() const {
int time_count = int(events.size());
std::vector<std::vector<std::pair<int, int>>> segment_tree(
std::max(1, 4 * time_count));
std::map<std::pair<int, int>, std::vector<int>> active;
auto add_interval = [&](auto &self, int node, int left, int right,
int query_left, int query_right,
std::pair<int, int> edge) -> void {
if (query_right <= left || right <= query_left) {
return;
}
if (query_left <= left && right <= query_right) {
segment_tree[node].push_back(edge);
return;
}
int middle = (left + right) / 2;
self(self, node * 2, left, middle, query_left, query_right, edge);
self(self, node * 2 + 1, middle, right, query_left, query_right, edge);
};
for (int time = 0; time < time_count; time++) {
const event ¤t = events[time];
std::pair<int, int> edge = {current.first, current.second};
if (current.type == event_type::add) {
active[edge].push_back(time);
} else if (current.type == event_type::remove) {
auto iterator = active.find(edge);
assert(iterator != active.end() && !iterator->second.empty());
if (iterator == active.end() || iterator->second.empty()) {
continue;
}
int start = iterator->second.back();
iterator->second.pop_back();
add_interval(add_interval, 1, 0, time_count, start, time, edge);
}
}
for (const auto &[edge, starts] : active) {
for (int start : starts) {
add_interval(add_interval, 1, 0, time_count, start, time_count, edge);
}
}
std::vector<bool> answers(query_count);
rollback_dsu dsu(vertex_count);
auto dfs = [&](auto &self, int node, int left, int right) -> void {
int state = dsu.snapshot();
for (auto [first, second] : segment_tree[node]) {
dsu.merge(first, second);
}
if (right - left == 1) {
const event ¤t = events[left];
if (current.type == event_type::query) {
answers[current.query_id] = dsu.same(current.first, current.second);
}
} else {
int middle = (left + right) / 2;
self(self, node * 2, left, middle);
self(self, node * 2 + 1, middle, right);
}
dsu.rollback(state);
};
if (time_count > 0) {
dfs(dfs, 1, 0, time_count);
}
return answers;
}
private:
void check_vertex(int vertex) const {
assert(0 <= vertex && vertex < vertex_count);
}
static void normalize(int &first, int &second) {
if (first > second) {
std::swap(first, second);
}
}
};
} // 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 + 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
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 type;
int first;
int second;
int query_id = -1;
};
int vertex_count = 0;
int query_count = 0;
std::vector<event> events;
offline_dynamic_connectivity() = default;
explicit offline_dynamic_connectivity(int n) : vertex_count(n) {
assert(n >= 0);
}
/// @brief Record the insertion of one copy of an undirected edge.
void add_edge(int first, int second) {
check_vertex(first);
check_vertex(second);
normalize(first, second);
events.push_back({event_type::add, first, second});
}
/// @brief Record the removal of the most recently added active copy.
void remove_edge(int first, int second) {
check_vertex(first);
check_vertex(second);
normalize(first, second);
events.push_back({event_type::remove, first, second});
}
/// @brief Record a connectivity query and return its answer index.
int add_query(int first, int second) {
check_vertex(first);
check_vertex(second);
int id = query_count++;
events.push_back({event_type::query, first, second, id});
return id;
}
/// @brief Solve all recorded queries in O((m + q) log m log n).
std::vector<bool> solve() const {
int time_count = int(events.size());
std::vector<std::vector<std::pair<int, int>>> segment_tree(
std::max(1, 4 * time_count));
std::map<std::pair<int, int>, std::vector<int>> active;
auto add_interval = [&](auto &self, int node, int left, int right,
int query_left, int query_right,
std::pair<int, int> edge) -> void {
if (query_right <= left || right <= query_left) {
return;
}
if (query_left <= left && right <= query_right) {
segment_tree[node].push_back(edge);
return;
}
int middle = (left + right) / 2;
self(self, node * 2, left, middle, query_left, query_right, edge);
self(self, node * 2 + 1, middle, right, query_left, query_right, edge);
};
for (int time = 0; time < time_count; time++) {
const event ¤t = events[time];
std::pair<int, int> edge = {current.first, current.second};
if (current.type == event_type::add) {
active[edge].push_back(time);
} else if (current.type == event_type::remove) {
auto iterator = active.find(edge);
assert(iterator != active.end() && !iterator->second.empty());
if (iterator == active.end() || iterator->second.empty()) {
continue;
}
int start = iterator->second.back();
iterator->second.pop_back();
add_interval(add_interval, 1, 0, time_count, start, time, edge);
}
}
for (const auto &[edge, starts] : active) {
for (int start : starts) {
add_interval(add_interval, 1, 0, time_count, start, time_count, edge);
}
}
std::vector<bool> answers(query_count);
rollback_dsu dsu(vertex_count);
auto dfs = [&](auto &self, int node, int left, int right) -> void {
int state = dsu.snapshot();
for (auto [first, second] : segment_tree[node]) {
dsu.merge(first, second);
}
if (right - left == 1) {
const event ¤t = events[left];
if (current.type == event_type::query) {
answers[current.query_id] = dsu.same(current.first, current.second);
}
} else {
int middle = (left + right) / 2;
self(self, node * 2, left, middle);
self(self, node * 2 + 1, middle, right);
}
dsu.rollback(state);
};
if (time_count > 0) {
dfs(dfs, 1, 0, time_count);
}
return answers;
}
private:
void check_vertex(int vertex) const {
assert(0 <= vertex && vertex < vertex_count);
}
static void normalize(int &first, int &second) {
if (first > second) {
std::swap(first, second);
}
}
};
} // namespace noya