Dynamic Connectivity
(ds/dynamic_connectivity/all.hpp)
- View this file on GitHub
- Last update: 2026-07-21 20:17:47+09:00
- Include:
#include "ds/dynamic_connectivity/all.hpp"
Included Headers
| Header | Use case |
|---|---|
online_dynamic_connectivity.hpp |
Operations must be answered immediately. |
offline_dynamic_connectivity.hpp |
The operation log may be processed together for faster deletion handling. |
Both structures maintain an undirected multigraph and erase edges by id.
Depends on
- Rollback DSU
(ds/dsu/rollback_dsu.hpp)
- Offline Dynamic Connectivity
(ds/dynamic_connectivity/offline_dynamic_connectivity.hpp)
- Online Dynamic Connectivity
(ds/dynamic_connectivity/online_dynamic_connectivity.hpp)
- Link-Cut Tree
(ds/dynamic_tree/link_cut_tree.hpp)
- Add Monoid
(monoid/add.hpp)
- Monoid Concept
(monoid/concept.hpp)
Verified with
Code
#ifndef M1UNE_DYNAMIC_CONNECTIVITY_ALL_HPP
#define M1UNE_DYNAMIC_CONNECTIVITY_ALL_HPP 1
#include "offline_dynamic_connectivity.hpp"
#include "online_dynamic_connectivity.hpp"
#endif // M1UNE_DYNAMIC_CONNECTIVITY_ALL_HPP#line 1 "ds/dynamic_connectivity/all.hpp"
#line 1 "ds/dynamic_connectivity/offline_dynamic_connectivity.hpp"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
#line 1 "ds/dsu/rollback_dsu.hpp"
#line 7 "ds/dsu/rollback_dsu.hpp"
namespace m1une {
namespace ds {
struct RollbackDsu {
private:
struct HistoryEntry {
int first;
int first_value;
int second;
int second_value;
};
int _n;
int _component_count;
std::vector<int> parent_or_size;
std::vector<HistoryEntry> history;
static int check_size(int n) {
assert(0 <= n);
return n;
}
public:
RollbackDsu() : RollbackDsu(0) {}
explicit RollbackDsu(int n)
: _n(check_size(n)), _component_count(_n), parent_or_size(_n, -1) {}
int size() const {
return _n;
}
bool empty() const {
return _n == 0;
}
int component_count() const {
return _component_count;
}
int history_size() const {
return int(history.size());
}
void reserve_history(int count) {
assert(0 <= count);
history.reserve(count);
}
int leader(int vertex) const {
assert(0 <= vertex && vertex < _n);
while (parent_or_size[vertex] >= 0) vertex = parent_or_size[vertex];
return vertex;
}
bool same(int first, int second) const {
return leader(first) == leader(second);
}
int group_size(int vertex) const {
return -parent_or_size[leader(vertex)];
}
int size(int vertex) const {
return group_size(vertex);
}
bool merge(int first, int second) {
first = leader(first);
second = leader(second);
if (first == second) {
history.push_back(HistoryEntry{-1, 0, -1, 0});
return false;
}
if (-parent_or_size[first] < -parent_or_size[second]) {
std::swap(first, second);
}
history.push_back(HistoryEntry{
first, parent_or_size[first], second, parent_or_size[second]
});
parent_or_size[first] += parent_or_size[second];
parent_or_size[second] = first;
_component_count--;
return true;
}
bool undo() {
if (history.empty()) return false;
const HistoryEntry entry = history.back();
history.pop_back();
if (entry.first == -1) return true;
parent_or_size[entry.first] = entry.first_value;
parent_or_size[entry.second] = entry.second_value;
_component_count++;
return true;
}
int snapshot() const {
return history_size();
}
void rollback(int state) {
assert(0 <= state && state <= history_size());
while (history_size() > state) undo();
}
std::vector<std::vector<int>> groups() const {
std::vector<int> leader_buffer(_n);
std::vector<int> group_sizes(_n, 0);
for (int vertex = 0; vertex < _n; vertex++) {
leader_buffer[vertex] = leader(vertex);
group_sizes[leader_buffer[vertex]]++;
}
std::vector<std::vector<int>> result(_n);
for (int vertex = 0; vertex < _n; vertex++) {
result[vertex].reserve(group_sizes[vertex]);
}
for (int vertex = 0; vertex < _n; vertex++) {
result[leader_buffer[vertex]].push_back(vertex);
}
result.erase(
std::remove_if(
result.begin(), result.end(),
[](const std::vector<int>& group) { return group.empty(); }
),
result.end()
);
return result;
}
};
} // namespace ds
} // namespace m1une
#line 10 "ds/dynamic_connectivity/offline_dynamic_connectivity.hpp"
namespace m1une {
namespace ds {
struct OfflineDynamicConnectivity {
private:
struct Edge {
int u;
int v;
int begin;
int end;
bool alive;
};
struct Query {
int u;
int v;
int time;
};
int _n;
int _time = 0;
std::vector<Edge> _edges;
std::vector<Query> _queries;
void dfs(
const std::vector<int>& offset,
const std::vector<std::pair<int, int>>& stored_edges,
const std::vector<int>& query_at,
std::vector<bool>& answer,
RollbackDsu& dsu,
int node,
int base
) const {
int snapshot = dsu.snapshot();
for (int i = offset[node]; i < offset[node + 1]; i++) {
auto [u, v] = stored_edges[i];
dsu.merge(u, v);
}
if (node >= base) {
int query_id = query_at[node - base];
if (query_id != -1) {
const Query& query = _queries[query_id];
answer[query_id] = dsu.same(query.u, query.v);
}
} else {
dfs(offset, stored_edges, query_at, answer, dsu, 2 * node, base);
dfs(offset, stored_edges, query_at, answer, dsu, 2 * node + 1, base);
}
dsu.rollback(snapshot);
}
public:
OfflineDynamicConnectivity() : OfflineDynamicConnectivity(0) {}
explicit OfflineDynamicConnectivity(int n) : _n(n) {
assert(0 <= n);
}
int size() const {
return _n;
}
int edge_count() const {
return int(_edges.size());
}
int query_count() const {
return int(_queries.size());
}
int operation_count() const {
return _time;
}
void reserve_edges(int count) {
assert(0 <= count);
_edges.reserve(count);
}
void reserve_queries(int count) {
assert(0 <= count);
_queries.reserve(count);
}
bool edge_alive(int edge_id) const {
assert(0 <= edge_id && edge_id < int(_edges.size()));
return _edges[edge_id].alive;
}
int add_edge(int u, int v) {
assert(0 <= u && u < _n);
assert(0 <= v && v < _n);
int edge_id = int(_edges.size());
_edges.push_back(Edge{u, v, _time, -1, true});
_time++;
return edge_id;
}
bool erase_edge(int edge_id) {
assert(0 <= edge_id && edge_id < int(_edges.size()));
Edge& edge = _edges[edge_id];
if (!edge.alive) return false;
edge.end = _time;
edge.alive = false;
_time++;
return true;
}
int add_query(int u, int v) {
assert(0 <= u && u < _n);
assert(0 <= v && v < _n);
int query_id = int(_queries.size());
_queries.push_back(Query{u, v, _time});
_time++;
return query_id;
}
std::vector<bool> solve() const {
std::vector<bool> answer(_queries.size(), false);
if (_queries.empty()) return answer;
if (_edges.empty()) {
for (int query_id = 0; query_id < int(_queries.size()); query_id++) {
answer[query_id] = _queries[query_id].u == _queries[query_id].v;
}
return answer;
}
int base = 1;
while (base < _time) base *= 2;
int node_count = 2 * base;
std::vector<int> count(node_count, 0);
for (const Edge& edge : _edges) {
int end = edge.alive ? _time : edge.end;
if (edge.begin < end && edge.u != edge.v) {
int left = edge.begin + base;
int right = end + base;
while (left < right) {
if (left & 1) count[left++]++;
if (right & 1) count[--right]++;
left /= 2;
right /= 2;
}
}
}
std::vector<int> offset(node_count + 1, 0);
for (int node = 1; node < node_count; node++) offset[node + 1] = offset[node] + count[node];
std::vector<int> cursor = offset;
std::vector<std::pair<int, int>> stored_edges(offset[node_count]);
for (const Edge& edge : _edges) {
int end = edge.alive ? _time : edge.end;
if (edge.begin >= end || edge.u == edge.v) continue;
int left = edge.begin + base;
int right = end + base;
while (left < right) {
if (left & 1) stored_edges[cursor[left]++] = {edge.u, edge.v}, left++;
if (right & 1) --right, stored_edges[cursor[right]++] = {edge.u, edge.v};
left /= 2;
right /= 2;
}
}
std::vector<int> query_at(base, -1);
for (int query_id = 0; query_id < int(_queries.size()); query_id++) {
query_at[_queries[query_id].time] = query_id;
}
RollbackDsu dsu(_n);
dsu.reserve_history(int(std::min<std::size_t>(_n, stored_edges.size())));
dfs(offset, stored_edges, query_at, answer, dsu, 1, base);
return answer;
}
};
} // namespace ds
} // namespace m1une
#line 1 "ds/dynamic_connectivity/online_dynamic_connectivity.hpp"
#line 6 "ds/dynamic_connectivity/online_dynamic_connectivity.hpp"
#include <cstdint>
#line 9 "ds/dynamic_connectivity/online_dynamic_connectivity.hpp"
#line 1 "monoid/add.hpp"
namespace m1une {
namespace monoid {
// Monoid for addition (Range Sum).
template <typename T>
struct Add {
using value_type = T;
static constexpr bool commutative = true;
// Returns the identity element for addition, which is 0.
static constexpr T id() {
return T(0);
}
// Returns the sum of a and b.
static constexpr T op(const T& a, const T& b) {
return a + b;
}
static constexpr T inv(const T& x) {
return -x;
}
};
} // namespace monoid
} // namespace m1une
#line 1 "ds/dynamic_tree/link_cut_tree.hpp"
#line 5 "ds/dynamic_tree/link_cut_tree.hpp"
#include <concepts>
#include <type_traits>
#line 9 "ds/dynamic_tree/link_cut_tree.hpp"
#line 1 "monoid/concept.hpp"
#line 5 "monoid/concept.hpp"
namespace m1une {
namespace monoid {
// Concept to check if a type satisfies the requirements of a Monoid.
// A Monoid must have a `value_type`, an identity element `id()`, and an associative binary operation `op()`.
template <typename M>
concept IsMonoid = requires(typename M::value_type a, typename M::value_type b) {
// 1. Must define `value_type`
typename M::value_type;
// 2. Must have a static method `id()` returning `value_type`
{ M::id() } -> std::same_as<typename M::value_type>;
// 3. Must have a static method `op(a, b)` returning `value_type`
{ M::op(a, b) } -> std::same_as<typename M::value_type>;
};
// Concept for groups. A type satisfying this concept must also obey the group
// laws; concepts can check the interface but not the algebraic properties.
template <typename M>
concept IsGroup = IsMonoid<M> && requires(typename M::value_type a) {
{ M::inv(a) } -> std::same_as<typename M::value_type>;
};
// Concept for commutative groups. Commutativity is a semantic requirement and
// cannot be checked by a C++ concept.
template <typename M>
concept IsCommutativeGroup = IsGroup<M>;
} // namespace monoid
} // namespace m1une
#line 11 "ds/dynamic_tree/link_cut_tree.hpp"
namespace m1une {
namespace ds {
template <m1une::monoid::IsCommutativeGroup Group>
struct LinkCutTree {
using T = typename Group::value_type;
private:
struct Node {
int left = -1;
int right = -1;
int parent = -1;
bool rev = false;
int size = 1;
int virtual_size = 0;
int all_size = 1;
T value = Group::id();
T prod = Group::id();
T rev_prod = Group::id();
T virtual_prod = Group::id();
T all_prod = Group::id();
};
struct EdgeInfo {
int u = -1;
int v = -1;
int node = -1;
bool alive = false;
};
std::vector<Node> _nodes;
std::vector<EdgeInfo> _edges;
std::vector<int> _path_buffer;
static T make_node_value(const T& value, int) {
return value;
}
static T make_node_value(T&& value, int) {
return std::move(value);
}
template <class U>
requires (!std::same_as<U, T>) && (
requires(U x) { Group::make(x); } ||
requires(U x, int i) { Group::make(x, i); } ||
std::convertible_to<U, T>
)
static T make_node_value(const U& value, int index) {
if constexpr (requires(U x) { Group::make(x); }) {
return Group::make(value);
} else if constexpr (requires(U x, int i) { Group::make(x, i); }) {
return Group::make(value, index);
} else {
return static_cast<T>(value);
}
}
int child_size(int node) const {
return node == -1 ? 0 : _nodes[node].size;
}
int child_all_size(int node) const {
return node == -1 ? 0 : _nodes[node].all_size;
}
T child_prod(int node) const {
return node == -1 ? Group::id() : _nodes[node].prod;
}
T child_rev_prod(int node) const {
return node == -1 ? Group::id() : _nodes[node].rev_prod;
}
T child_all_prod(int node) const {
return node == -1 ? Group::id() : _nodes[node].all_prod;
}
T node_subtree_prod(int node) const {
const Node& x = _nodes[node];
return Group::op(x.value, x.virtual_prod);
}
int node_subtree_size(int node) const {
return 1 + _nodes[node].virtual_size;
}
bool is_splay_root(int node) const {
int parent = _nodes[node].parent;
return parent == -1 || (_nodes[parent].left != node && _nodes[parent].right != node);
}
void update(int node) {
Node& x = _nodes[node];
x.size = 1 + child_size(x.left) + child_size(x.right);
x.all_size = 1 + x.virtual_size + child_all_size(x.left) + child_all_size(x.right);
x.prod = Group::op(Group::op(child_prod(x.left), x.value), child_prod(x.right));
x.rev_prod = Group::op(Group::op(child_rev_prod(x.right), x.value), child_rev_prod(x.left));
x.all_prod = Group::op(Group::op(child_all_prod(x.left), x.value),
Group::op(x.virtual_prod, child_all_prod(x.right)));
}
void add_virtual_child(int node, int child) {
if (child == -1) return;
Node& x = _nodes[node];
x.virtual_size += _nodes[child].all_size;
x.virtual_prod = Group::op(x.virtual_prod, _nodes[child].all_prod);
}
void remove_virtual_child(int node, int child) {
if (child == -1) return;
Node& x = _nodes[node];
x.virtual_size -= _nodes[child].all_size;
x.virtual_prod = Group::op(x.virtual_prod, Group::inv(_nodes[child].all_prod));
}
void apply_reverse(int node) {
if (node == -1) return;
Node& x = _nodes[node];
std::swap(x.left, x.right);
std::swap(x.prod, x.rev_prod);
x.rev = !x.rev;
}
void push(int node) {
if (node == -1 || !_nodes[node].rev) return;
apply_reverse(_nodes[node].left);
apply_reverse(_nodes[node].right);
_nodes[node].rev = false;
}
void push_to(int node) {
_path_buffer.clear();
int cur = node;
_path_buffer.push_back(cur);
while (!is_splay_root(cur)) {
cur = _nodes[cur].parent;
_path_buffer.push_back(cur);
}
for (int i = int(_path_buffer.size()) - 1; i >= 0; i--) push(_path_buffer[i]);
}
void rotate(int node) {
int parent = _nodes[node].parent;
int grand = _nodes[parent].parent;
bool is_right = _nodes[parent].right == node;
int middle = is_right ? _nodes[node].left : _nodes[node].right;
if (!is_splay_root(parent)) {
if (_nodes[grand].left == parent) {
_nodes[grand].left = node;
} else {
_nodes[grand].right = node;
}
}
_nodes[node].parent = grand;
if (is_right) {
_nodes[node].left = parent;
_nodes[parent].right = middle;
} else {
_nodes[node].right = parent;
_nodes[parent].left = middle;
}
if (middle != -1) _nodes[middle].parent = parent;
_nodes[parent].parent = node;
update(parent);
update(node);
}
void splay(int node) {
push_to(node);
while (!is_splay_root(node)) {
int parent = _nodes[node].parent;
int grand = _nodes[parent].parent;
if (!is_splay_root(parent)) {
bool zig_zig = (_nodes[parent].left == node) == (_nodes[grand].left == parent);
rotate(zig_zig ? parent : node);
}
rotate(node);
}
}
int access(int node) {
int last = -1;
for (int cur = node; cur != -1; cur = _nodes[cur].parent) {
splay(cur);
add_virtual_child(cur, _nodes[cur].right);
remove_virtual_child(cur, last);
_nodes[cur].right = last;
if (last != -1) _nodes[last].parent = cur;
update(cur);
last = cur;
}
splay(node);
return last;
}
void check_vertex(int v) const {
assert(0 <= v && v < int(_nodes.size()));
}
void check_edge(int edge_id) const {
assert(0 <= edge_id && edge_id < int(_edges.size()));
}
public:
LinkCutTree() = default;
explicit LinkCutTree(int n) {
assert(0 <= n);
_nodes.reserve(n);
for (int i = 0; i < n; i++) add_vertex();
}
explicit LinkCutTree(const std::vector<T>& values) {
_nodes.reserve(values.size());
for (int i = 0; i < int(values.size()); i++) add_vertex(values[i]);
}
explicit LinkCutTree(std::vector<T>&& values) {
_nodes.reserve(values.size());
for (int i = 0; i < int(values.size()); i++) add_vertex(std::move(values[i]));
}
template <class U>
requires (!std::same_as<U, T>) && (
requires(U x) { Group::make(x); } ||
requires(U x, int i) { Group::make(x, i); } ||
std::convertible_to<U, T>
)
explicit LinkCutTree(const std::vector<U>& values) {
_nodes.reserve(values.size());
for (int i = 0; i < int(values.size()); i++) add_vertex(make_node_value(values[i], i));
}
int size() const {
return int(_nodes.size());
}
bool empty() const {
return _nodes.empty();
}
int add_vertex(const T& value = Group::id()) {
Node node;
node.value = value;
node.prod = value;
node.rev_prod = value;
node.all_prod = value;
_nodes.push_back(std::move(node));
return int(_nodes.size()) - 1;
}
int add_vertex(T&& value) {
Node node;
node.value = std::move(value);
node.prod = node.value;
node.rev_prod = node.value;
node.all_prod = node.value;
_nodes.push_back(std::move(node));
return int(_nodes.size()) - 1;
}
template <class U>
requires (!std::same_as<std::remove_cvref_t<U>, T>) && (
requires(U x) { Group::make(x); } ||
requires(U x, int i) { Group::make(x, i); } ||
std::convertible_to<U, T>
)
int add_vertex(const U& value) {
return add_vertex(make_node_value(value, size()));
}
int edge_count() const {
return int(_edges.size());
}
bool edge_alive(int edge_id) const {
check_edge(edge_id);
return _edges[edge_id].alive;
}
int edge_node(int edge_id) const {
check_edge(edge_id);
return _edges[edge_id].node;
}
std::pair<int, int> edge_endpoints(int edge_id) const {
check_edge(edge_id);
return {_edges[edge_id].u, _edges[edge_id].v};
}
const T& get(int v) const {
check_vertex(v);
return _nodes[v].value;
}
const T& operator[](int v) const {
return get(v);
}
void set(int v, const T& value) {
check_vertex(v);
access(v);
_nodes[v].value = value;
update(v);
}
void set(int v, T&& value) {
check_vertex(v);
access(v);
_nodes[v].value = std::move(value);
update(v);
}
template <class U>
requires (!std::same_as<std::remove_cvref_t<U>, T>) && (
requires(U x) { Group::make(x); } ||
requires(U x, int i) { Group::make(x, i); } ||
std::convertible_to<U, T>
)
void set(int v, const U& value) {
set(v, make_node_value(value, v));
}
// Makes `v` the represented root of its component.
void evert(int v) {
check_vertex(v);
access(v);
apply_reverse(v);
}
// Alias for `evert(v)`; changes the represented root to `v`.
void reroot(int v) {
evert(v);
}
// Returns the current represented root of `v`'s component.
int component_root(int v) {
check_vertex(v);
access(v);
int cur = v;
push(cur);
while (_nodes[cur].left != -1) {
cur = _nodes[cur].left;
push(cur);
}
splay(cur);
return cur;
}
// Alias for `component_root(v)`.
int root(int v) {
return component_root(v);
}
bool connected(int u, int v) {
check_vertex(u);
check_vertex(v);
if (u == v) return true;
return component_root(u) == component_root(v);
}
bool same(int u, int v) {
return connected(u, v);
}
// Links two components. Internally calls `evert(u)`, so the represented root may change.
bool link(int u, int v) {
check_vertex(u);
check_vertex(v);
if (u == v) return false;
evert(u);
if (component_root(v) == u) return false;
access(v);
_nodes[u].parent = v;
add_virtual_child(v, u);
update(v);
return true;
}
// Links `child` under `parent`. This is the same operation as `link(child, parent)`;
// it internally calls `evert(child)`, so that side's represented root may change.
bool link_parent(int child, int parent) {
return link(child, parent);
}
int link_edge(int u, int v, const T& value = Group::id()) {
check_vertex(u);
check_vertex(v);
if (u == v || connected(u, v)) return -1;
int edge_id = int(_edges.size());
int node = add_vertex(value);
_edges.push_back(EdgeInfo{u, v, node, true});
bool ok1 = link(u, node);
bool ok2 = link(node, v);
assert(ok1 && ok2);
return edge_id;
}
int link_edge(int u, int v, T&& value) {
check_vertex(u);
check_vertex(v);
if (u == v || connected(u, v)) return -1;
int edge_id = int(_edges.size());
int node = add_vertex(std::move(value));
_edges.push_back(EdgeInfo{u, v, node, true});
bool ok1 = link(u, node);
bool ok2 = link(node, v);
assert(ok1 && ok2);
return edge_id;
}
template <class U>
requires (!std::same_as<std::remove_cvref_t<U>, T>) && (
requires(U x) { Group::make(x); } ||
requires(U x, int i) { Group::make(x, i); } ||
std::convertible_to<U, T>
)
int link_edge(int u, int v, const U& value) {
check_vertex(u);
check_vertex(v);
if (u == v || connected(u, v)) return -1;
return link_edge(u, v, make_node_value(value, size()));
}
// Cuts edge `(u, v)`. Internally calls `evert(u)`, so the represented root may change.
bool cut(int u, int v) {
check_vertex(u);
check_vertex(v);
if (u == v) return false;
evert(u);
access(v);
if (_nodes[v].left != u || _nodes[u].right != -1) return false;
_nodes[v].left = -1;
_nodes[u].parent = -1;
update(v);
return true;
}
// Cuts the parent edge of `v` in the current represented-root orientation.
// Unlike `cut(u, v)`, this does not call `evert`.
bool cut_parent(int v) {
check_vertex(v);
access(v);
int left = _nodes[v].left;
if (left == -1) return false;
_nodes[v].left = -1;
_nodes[left].parent = -1;
update(v);
return true;
}
bool cut_edge(int edge_id) {
check_edge(edge_id);
EdgeInfo& edge = _edges[edge_id];
if (!edge.alive) return false;
bool ok1 = cut(edge.u, edge.node);
bool ok2 = cut(edge.node, edge.v);
if (ok1 && ok2) edge.alive = false;
return ok1 && ok2;
}
const T& get_edge(int edge_id) const {
return get(edge_node(edge_id));
}
void set_edge(int edge_id, const T& value) {
set(edge_node(edge_id), value);
}
void set_edge(int edge_id, T&& value) {
set(edge_node(edge_id), std::move(value));
}
template <class U>
requires (!std::same_as<std::remove_cvref_t<U>, T>) && (
requires(U x) { Group::make(x); } ||
requires(U x, int i) { Group::make(x, i); } ||
std::convertible_to<U, T>
)
void set_edge(int edge_id, const U& value) {
set(edge_node(edge_id), make_node_value(value, edge_node(edge_id)));
}
// Returns the path product from `u` to `v`. Internally calls `evert(u)`,
// so the represented root may change.
T prod(int u, int v) {
check_vertex(u);
check_vertex(v);
assert(connected(u, v));
evert(u);
access(v);
return _nodes[v].prod;
}
// Alias for `prod(u, v)`. Internally calls `evert(u)`,
// so the represented root may change.
T path_prod(int u, int v) {
return prod(u, v);
}
// Returns the number of vertices on path `u`-`v`. Internally calls `evert(u)`,
// so the represented root may change.
int path_size(int u, int v) {
check_vertex(u);
check_vertex(v);
assert(connected(u, v));
evert(u);
access(v);
return _nodes[v].size;
}
// Returns the `k`-th vertex on path `u`-`v`. Internally calls `evert(u)`,
// so the represented root may change.
int kth_vertex(int u, int v, int k) {
check_vertex(u);
check_vertex(v);
assert(connected(u, v));
evert(u);
access(v);
assert(0 <= k && k < _nodes[v].size);
int cur = v;
while (true) {
push(cur);
int left_size = child_size(_nodes[cur].left);
if (k < left_size) {
cur = _nodes[cur].left;
} else if (k == left_size) {
splay(cur);
return cur;
} else {
k -= left_size + 1;
cur = _nodes[cur].right;
}
}
}
int lca(int u, int v) {
check_vertex(u);
check_vertex(v);
if (!connected(u, v)) return -1;
if (u == v) return u;
access(u);
return access(v);
}
// Returns the aggregate of `v`'s subtree when the represented tree is rooted at `root`.
// Internally calls `evert(root)`, so the represented root may change.
T subtree_prod(int root, int v) {
check_vertex(root);
check_vertex(v);
assert(connected(root, v));
evert(root);
access(v);
return node_subtree_prod(v);
}
// Returns the aggregate of `v`'s subtree with respect to the current represented root.
T subtree_prod(int v) {
check_vertex(v);
access(v);
return node_subtree_prod(v);
}
// Returns the size of `v`'s subtree when the represented tree is rooted at `root`.
// Internally calls `evert(root)`, so the represented root may change.
int subtree_size(int root, int v) {
check_vertex(root);
check_vertex(v);
assert(connected(root, v));
evert(root);
access(v);
return node_subtree_size(v);
}
// Returns the size of `v`'s subtree with respect to the current represented root.
int subtree_size(int v) {
check_vertex(v);
access(v);
return node_subtree_size(v);
}
// Returns the aggregate of the whole connected component containing `v`.
T component_prod(int v) {
int r = root(v);
return subtree_prod(r, r);
}
// Returns the number of vertices in the connected component containing `v`.
int component_size(int v) {
int r = root(v);
return subtree_size(r, r);
}
// Returns the child of `root` that lies on path `root`-`v`.
int child_toward(int root, int v) {
check_vertex(root);
check_vertex(v);
assert(root != v);
assert(connected(root, v));
return kth_vertex(root, v, 1);
}
// Returns the aggregate of the entire branch of `root` that contains `v`.
T branch_prod(int root, int v) {
check_vertex(root);
check_vertex(v);
assert(root != v);
int child = child_toward(root, v);
return subtree_prod(root, child);
}
// Returns the size of the entire branch of `root` that contains `v`.
int branch_size(int root, int v) {
check_vertex(root);
check_vertex(v);
assert(root != v);
int child = child_toward(root, v);
return subtree_size(root, child);
}
// Returns the parent of `v` when rooted at `root`, or `-1` if `v == root`.
int parent(int root, int v) {
check_vertex(root);
check_vertex(v);
if (root == v) return -1;
assert(connected(root, v));
int d = path_size(root, v);
assert(2 <= d);
return kth_vertex(root, v, d - 2);
}
// Returns `v`'s rooted subtree aggregate excluding the child-side subtree.
T subtree_prod_excluding_child(int root, int v, int child) {
check_vertex(root);
check_vertex(v);
check_vertex(child);
assert(parent(root, child) == v);
T whole = subtree_prod(root, v);
T sub = subtree_prod(root, child);
return Group::op(whole, Group::inv(sub));
}
// Returns `v`'s rooted subtree size excluding the child-side subtree.
int subtree_size_excluding_child(int root, int v, int child) {
check_vertex(root);
check_vertex(v);
check_vertex(child);
assert(parent(root, child) == v);
return subtree_size(root, v) - subtree_size(root, child);
}
};
} // namespace ds
} // namespace m1une
#line 12 "ds/dynamic_connectivity/online_dynamic_connectivity.hpp"
namespace m1une {
namespace ds {
struct OnlineDynamicConnectivity {
private:
using Forest = LinkCutTree<m1une::monoid::Add<int>>;
struct Edge {
int u;
int v;
bool alive;
bool tree;
int previous_u = -1;
int next_u = -1;
int previous_v = -1;
int next_v = -1;
};
int _n;
int _component_count;
int _active_edge_count = 0;
Forest _forest;
std::vector<Edge> _edges;
std::vector<int> _tree_head;
std::vector<int> _non_tree_head;
std::vector<std::uint32_t> _visited;
std::vector<std::uint32_t> _edge_visited;
std::uint32_t _visit_token = 0;
std::vector<int> _stack;
std::vector<int> _component;
int endpoint_side(const Edge& edge, int v) const {
return edge.u == v ? 0 : 1;
}
int& previous(Edge& edge, int side) {
return side == 0 ? edge.previous_u : edge.previous_v;
}
int& next(Edge& edge, int side) {
return side == 0 ? edge.next_u : edge.next_v;
}
int next(const Edge& edge, int side) const {
return side == 0 ? edge.next_u : edge.next_v;
}
void insert_one(std::vector<int>& head, int edge_id, int v, int side) {
Edge& edge = _edges[edge_id];
int old_head = head[v];
previous(edge, side) = -1;
next(edge, side) = old_head;
if (old_head != -1) {
Edge& old_edge = _edges[old_head];
previous(old_edge, endpoint_side(old_edge, v)) = edge_id;
}
head[v] = edge_id;
}
void erase_one(std::vector<int>& head, int edge_id, int v, int side) {
Edge& edge = _edges[edge_id];
int previous_id = previous(edge, side);
int next_id = next(edge, side);
if (previous_id == -1) {
head[v] = next_id;
} else {
Edge& previous_edge = _edges[previous_id];
next(previous_edge, endpoint_side(previous_edge, v)) = next_id;
}
if (next_id != -1) {
Edge& next_edge = _edges[next_id];
previous(next_edge, endpoint_side(next_edge, v)) = previous_id;
}
previous(edge, side) = -1;
next(edge, side) = -1;
}
void insert_incident(std::vector<int>& head, int edge_id) {
const Edge& edge = _edges[edge_id];
int u = edge.u;
int v = edge.v;
insert_one(head, edge_id, u, 0);
if (u != v) insert_one(head, edge_id, v, 1);
}
void erase_incident(std::vector<int>& head, int edge_id) {
const Edge& edge = _edges[edge_id];
int u = edge.u;
int v = edge.v;
erase_one(head, edge_id, u, 0);
if (u != v) erase_one(head, edge_id, v, 1);
}
void make_tree_edge(int edge_id) {
Edge& edge = _edges[edge_id];
assert(edge.alive && !edge.tree && edge.u != edge.v);
erase_incident(_non_tree_head, edge_id);
bool linked = _forest.link(edge.u, edge.v);
assert(linked);
edge.tree = true;
insert_incident(_tree_head, edge_id);
_component_count--;
}
void collect_component(int start) {
_visit_token++;
if (_visit_token == 0) {
std::fill(_visited.begin(), _visited.end(), 0);
std::fill(_edge_visited.begin(), _edge_visited.end(), 0);
_visit_token = 1;
}
_stack.clear();
_component.clear();
_visited[start] = _visit_token;
_stack.push_back(start);
while (!_stack.empty()) {
int v = _stack.back();
_stack.pop_back();
_component.push_back(v);
for (int edge_id = _tree_head[v]; edge_id != -1;) {
const Edge& edge = _edges[edge_id];
int edge_side = endpoint_side(edge, v);
edge_id = next(edge, edge_side);
int to = edge.u ^ edge.v ^ v;
if (_visited[to] == _visit_token) continue;
_visited[to] = _visit_token;
_stack.push_back(to);
}
}
}
void reconnect(int u, int v) {
int start = _forest.component_size(u) <= _forest.component_size(v) ? u : v;
collect_component(start);
int replacement = -1;
for (int x : _component) {
for (int edge_id = _non_tree_head[x]; edge_id != -1;) {
const Edge& edge = _edges[edge_id];
int edge_side = endpoint_side(edge, x);
int current_edge = edge_id;
edge_id = next(edge, edge_side);
if (_edge_visited[current_edge] == _visit_token) continue;
_edge_visited[current_edge] = _visit_token;
if (_visited[edge.u] != _visit_token || _visited[edge.v] != _visit_token) {
replacement = current_edge;
break;
}
}
if (replacement != -1) break;
}
if (replacement != -1) make_tree_edge(replacement);
}
public:
OnlineDynamicConnectivity() : OnlineDynamicConnectivity(0) {}
explicit OnlineDynamicConnectivity(int n)
: _n(n),
_component_count(n),
_forest(n),
_tree_head(n, -1),
_non_tree_head(n, -1),
_visited(n, 0) {
assert(0 <= n);
}
int size() const {
return _n;
}
int edge_count() const {
return int(_edges.size());
}
int active_edge_count() const {
return _active_edge_count;
}
int component_count() const {
return _component_count;
}
void reserve_edges(int count) {
assert(0 <= count);
_edges.reserve(count);
_edge_visited.reserve(count);
}
bool edge_alive(int edge_id) const {
assert(0 <= edge_id && edge_id < int(_edges.size()));
return _edges[edge_id].alive;
}
std::pair<int, int> edge_endpoints(int edge_id) const {
assert(0 <= edge_id && edge_id < int(_edges.size()));
return {_edges[edge_id].u, _edges[edge_id].v};
}
bool connected(int u, int v) {
assert(0 <= u && u < _n);
assert(0 <= v && v < _n);
return _forest.connected(u, v);
}
bool same(int u, int v) {
return connected(u, v);
}
int component_size(int v) {
assert(0 <= v && v < _n);
return _forest.component_size(v);
}
int add_edge(int u, int v) {
assert(0 <= u && u < _n);
assert(0 <= v && v < _n);
bool is_tree = u != v && _forest.link(u, v);
int edge_id = int(_edges.size());
Edge edge;
edge.u = u;
edge.v = v;
edge.alive = true;
edge.tree = is_tree;
_edges.push_back(edge);
_edge_visited.push_back(0);
_active_edge_count++;
if (is_tree) {
insert_incident(_tree_head, edge_id);
_component_count--;
} else {
insert_incident(_non_tree_head, edge_id);
}
return edge_id;
}
bool erase_edge(int edge_id) {
assert(0 <= edge_id && edge_id < int(_edges.size()));
Edge& edge = _edges[edge_id];
if (!edge.alive) return false;
edge.alive = false;
_active_edge_count--;
if (!edge.tree) {
erase_incident(_non_tree_head, edge_id);
return true;
}
erase_incident(_tree_head, edge_id);
bool cut = _forest.cut(edge.u, edge.v);
assert(cut);
_component_count++;
reconnect(edge.u, edge.v);
return true;
}
};
} // namespace ds
} // namespace m1une
#line 6 "ds/dynamic_connectivity/all.hpp"