Online Dynamic Connectivity
(ds/dynamic_connectivity/online_dynamic_connectivity.hpp)
- View this file on GitHub
- Last update: 2026-07-21 20:17:47+09:00
- Include:
#include "ds/dynamic_connectivity/online_dynamic_connectivity.hpp"
Overview
OnlineDynamicConnectivity maintains connectivity in an undirected multigraph
while edges are inserted and erased. Every operation is processed immediately;
the complete operation sequence does not need to be known in advance.
The structure maintains a spanning forest with a link-cut tree. Non-tree edges are stored in intrusive per-vertex lists, so insertion, deletion, and promotion between edge classes do not allocate or perform balanced-tree operations. When a tree edge is erased, it enumerates the smaller resulting tree and searches its incident non-tree edges for a replacement.
Parallel edges and self-loops are supported. Edges are erased by the id returned
from add_edge, so parallel copies remain distinct.
Methods
| Method | Description | Complexity |
|---|---|---|
OnlineDynamicConnectivity() |
Creates an empty graph. | O(1) |
OnlineDynamicConnectivity(int n) |
Creates n isolated vertices. |
O(N) |
int size() const |
Returns the number of vertices. | O(1) |
int edge_count() const |
Returns the number of edge ids ever created. | O(1) |
int active_edge_count() const |
Returns the number of currently active edges. | O(1) |
int component_count() const |
Returns the current number of connected components. | O(1) |
void reserve_edges(int count) |
Reserves storage for edge ids. |
O(M) when reallocation occurs |
bool edge_alive(int id) const |
Returns whether edge id is active. |
O(1) |
pair<int, int> edge_endpoints(int id) const |
Returns the endpoints of edge id. |
O(1) |
bool connected(int u, int v) |
Returns whether u and v are connected. |
Amortized O(log N)
|
bool same(int u, int v) |
Alias for connected. |
Amortized O(log N)
|
int component_size(int v) |
Returns the number of vertices in v’s component. |
Amortized O(log N)
|
int add_edge(int u, int v) |
Inserts an edge and returns its id. | Amortized O(log N)
|
bool erase_edge(int id) |
Erases an active edge. Returns false if it was already erased. | See below |
Deleting a non-tree edge costs logarithmic set maintenance. If a tree edge is
deleted, let S be the smaller resulting component and let I be the number
of non-tree-edge incidences touching vertices of S. Replacement search costs
O(|S| + I + log N).
This deterministic strategy is compact and fast for typical sparse competitive
programming workloads. When all operations are known beforehand, prefer
OfflineDynamicConnectivity, whose deletion handling has a stronger batch
bound.
Example
#include "ds/dynamic_connectivity/online_dynamic_connectivity.hpp"
#include <iostream>
int main() {
m1une::ds::OnlineDynamicConnectivity graph(4);
int e01 = graph.add_edge(0, 1);
int e12 = graph.add_edge(1, 2);
int e02 = graph.add_edge(0, 2);
std::cout << graph.connected(0, 2) << '\n'; // 1
graph.erase_edge(e12);
std::cout << graph.connected(0, 2) << '\n'; // 1, through e02
graph.erase_edge(e02);
std::cout << graph.connected(0, 2) << '\n'; // 0
graph.erase_edge(e01);
}
Depends on
- Link-Cut Tree
(ds/dynamic_tree/link_cut_tree.hpp)
- Add Monoid
(monoid/add.hpp)
- Monoid Concept
(monoid/concept.hpp)
Required by
Verified with
Code
#ifndef M1UNE_ONLINE_DYNAMIC_CONNECTIVITY_HPP
#define M1UNE_ONLINE_DYNAMIC_CONNECTIVITY_HPP 1
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
#include "../../monoid/add.hpp"
#include "../dynamic_tree/link_cut_tree.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
#endif // M1UNE_ONLINE_DYNAMIC_CONNECTIVITY_HPP#line 1 "ds/dynamic_connectivity/online_dynamic_connectivity.hpp"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
#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