description: Maintain the unique minimum spanning forest under edge insertions. Represent every selected edge by an extra Link-Cut Tree vertex carrying (weight,id), while original vertices carry minus infinity. A cycle-forming insertion exposes its endpoint path: the heaviest selected edge is replaced exactly when it is heavier. Removed edge vertices are reused, so at most n-1 extra nodes are needed even for an arbitrarily long insertion stream.¶
incremental_msf.hpp¶
Maintain the unique minimum spanning forest under edge insertions. Represent every selected edge by an extra Link-Cut Tree vertex carrying (weight,id), while original vertices carry minus infinity. A cycle-forming insertion exposes its endpoint path: the heaviest selected edge is replaced exactly when it is heavier. Removed edge vertices are reused, so at most n-1 extra nodes are needed even for an arbitrarily long insertion stream.
Verified by incremental_minimum_spanning_forest.
只增加边时维护最小生成森林，并报告新边替换了哪条更重的树边。
Implementation¶
#ifndef NOYA_INCREMENTAL_MSF_HPP
#define NOYA_INCREMENTAL_MSF_HPP 1
/// @complexity Time: Amortized O(log n) per inserted edge.
/// Space: O(n), independent of the number of rejected edges.
#include "noya/link_cut_tree.hpp"
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
namespace incremental_msf_detail {
template <class Weight> struct maximum_edge_monoid {
using value_type = std::pair<Weight, int>;
static value_type unit() {
return {std::numeric_limits<Weight>::lowest(), -1};
}
static value_type op(const value_type &left, const value_type &right) {
return std::max(left, right);
}
};
} // namespace incremental_msf_detail
/// @brief Maintain the unique minimum spanning forest under edge insertions.
/// Represent every selected edge by an extra Link-Cut Tree vertex carrying
/// (weight,id), while original vertices carry minus infinity. A cycle-forming
/// insertion exposes its endpoint path: the heaviest selected edge is replaced
/// exactly when it is heavier. Removed edge vertices are reused, so at most
/// n-1 extra nodes are needed even for an arbitrarily long insertion stream.
template <class Weight> class incremental_minimum_spanning_forest {
using monoid = incremental_msf_detail::maximum_edge_monoid<Weight>;
using value_type = typename monoid::value_type;
public:
explicit incremental_minimum_spanning_forest(int n) : vertex_count_(n) {
assert(n >= 0);
forest_.build(std::vector<value_type>(
std::size_t(n) + std::size_t(std::max(0, n - 1)), monoid::unit()));
endpoints_.resize(std::size_t(std::max(0, n - 1)));
}
/// @brief Insert an edge with a globally unique weight and ID. Return -1
/// when it increases the forest size; otherwise return the removed edge ID,
/// which equals id itself when the new edge is rejected.
int add_edge(int first, int second, Weight weight, int id) {
assert(0 <= first && first < vertex_count_);
assert(0 <= second && second < vertex_count_);
if (!forest_.connected(first, second)) {
assert(used_slots_ < std::max(0, vertex_count_ - 1));
install(used_slots_++, first, second, weight, id);
return -1;
}
auto [maximum_weight, maximum_id] =
forest_.path_product(first, second);
if (weight > maximum_weight) {
return id;
}
int slot = id_to_slot_[maximum_id];
auto [old_first, old_second] = endpoints_[slot];
int edge_vertex = vertex_count_ + slot;
bool cut_first = forest_.cut(edge_vertex, old_first);
bool cut_second = forest_.cut(edge_vertex, old_second);
assert(cut_first && cut_second);
install(slot, first, second, weight, id);
return maximum_id;
}
private:
int vertex_count_ = 0;
int used_slots_ = 0;
link_cut_tree<monoid> forest_;
std::vector<std::pair<int, int>> endpoints_;
std::vector<int> id_to_slot_;
void install(int slot, int first, int second, Weight weight, int id) {
assert(id >= 0);
if (int(id_to_slot_.size()) <= id) {
id_to_slot_.resize(id + 1, -1);
}
id_to_slot_[id] = slot;
endpoints_[slot] = {first, second};
int edge_vertex = vertex_count_ + slot;
forest_.set(edge_vertex, {weight, id});
bool linked_first = forest_.link(first, edge_vertex);
bool linked_second = forest_.link(second, edge_vertex);
assert(linked_first && linked_second);
}
};
} // namespace noya
#endif // NOYA_INCREMENTAL_MSF_HPP
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>
/// @complexity Time: Amortized O(log n) per inserted edge.
/// Space: O(n), independent of the number of rejected edges.
/// @complexity Time: Amortized O(log n) per dynamic-tree operation.
/// Space: O(n).
namespace noya {
/// @brief Link-Cut Tree for a dynamic forest with point assignment and ordered
/// path products; all operations take amortized O(log n) time.
template <class Monoid> struct link_cut_tree {
using value_type = typename Monoid::value_type;
struct node {
int child[2] = {-1, -1};
int parent = -1;
int auxiliary_size = 1;
bool reversed = false;
value_type value;
value_type forward_product;
value_type backward_product;
explicit node(const value_type &initial)
: value(initial), forward_product(initial), backward_product(initial) {}
};
std::vector<node> nodes;
link_cut_tree() = default;
explicit link_cut_tree(const std::vector<value_type> &values) {
build(values);
}
/// @brief Reset to isolated vertices carrying the given values.
void build(const std::vector<value_type> &values) {
nodes.clear();
nodes.reserve(values.size());
splay_stack.clear();
splay_stack.reserve(values.size());
for (const value_type &value : values) {
nodes.emplace_back(value);
}
}
/// @brief Return the number of vertices.
int size() const { return int(nodes.size()); }
/// @brief Return whether two vertices are in the same represented tree.
bool connected(int first, int second) {
check_vertex(first);
check_vertex(second);
return first == second || find_root(first) == find_root(second);
}
/// @brief Add an edge between different trees; return false if it would
/// create a cycle.
bool link(int first, int second) {
check_vertex(first);
check_vertex(second);
if (connected(first, second)) {
return false;
}
make_root(first);
nodes[first].parent = second;
return true;
}
/// @brief Remove an existing edge; return false when the vertices are not
/// directly adjacent.
bool cut(int first, int second) {
check_vertex(first);
check_vertex(second);
make_root(first);
access(second);
if (nodes[second].child[0] != first || nodes[first].child[1] != -1) {
return false;
}
nodes[second].child[0] = -1;
nodes[first].parent = -1;
pull(second);
return true;
}
/// @brief Change one vertex value.
void set(int vertex, const value_type &value) {
check_vertex(vertex);
access(vertex);
nodes[vertex].value = value;
pull(vertex);
}
/// @brief Return one vertex value.
const value_type &get(int vertex) {
check_vertex(vertex);
access(vertex);
return nodes[vertex].value;
}
/// @brief Return the ordered monoid product on the path from first to
/// second; the vertices must be connected.
value_type path_product(int first, int second) {
check_vertex(first);
check_vertex(second);
assert(connected(first, second));
make_root(first);
access(second);
return nodes[second].forward_product;
}
/// @brief Return the number of vertices on a connected path.
int path_size(int first, int second) {
check_vertex(first);
check_vertex(second);
assert(connected(first, second));
make_root(first);
access(second);
return nodes[second].auxiliary_size;
}
private:
std::vector<int> splay_stack;
void check_vertex(int vertex) const {
assert(0 <= vertex && vertex < size());
}
bool is_auxiliary_root(int vertex) const {
int parent = nodes[vertex].parent;
return parent == -1 || (nodes[parent].child[0] != vertex &&
nodes[parent].child[1] != vertex);
}
int auxiliary_size(int vertex) const {
return vertex == -1 ? 0 : nodes[vertex].auxiliary_size;
}
value_type forward_product(int vertex) const {
return vertex == -1 ? Monoid::unit() : nodes[vertex].forward_product;
}
value_type backward_product(int vertex) const {
return vertex == -1 ? Monoid::unit() : nodes[vertex].backward_product;
}
void pull(int vertex) {
int left = nodes[vertex].child[0];
int right = nodes[vertex].child[1];
nodes[vertex].auxiliary_size =
1 + auxiliary_size(left) + auxiliary_size(right);
nodes[vertex].forward_product =
Monoid::op(Monoid::op(forward_product(left), nodes[vertex].value),
forward_product(right));
nodes[vertex].backward_product =
Monoid::op(Monoid::op(backward_product(right), nodes[vertex].value),
backward_product(left));
}
void apply_reverse(int vertex) {
if (vertex == -1) {
return;
}
std::swap(nodes[vertex].child[0], nodes[vertex].child[1]);
std::swap(nodes[vertex].forward_product,
nodes[vertex].backward_product);
nodes[vertex].reversed = !nodes[vertex].reversed;
}
void push(int vertex) {
if (!nodes[vertex].reversed) {
return;
}
apply_reverse(nodes[vertex].child[0]);
apply_reverse(nodes[vertex].child[1]);
nodes[vertex].reversed = false;
}
void rotate(int vertex) {
int parent = nodes[vertex].parent;
int grandparent = nodes[parent].parent;
int direction = nodes[parent].child[1] == vertex;
int middle = nodes[vertex].child[direction ^ 1];
if (!is_auxiliary_root(parent)) {
nodes[grandparent].child[nodes[grandparent].child[1] == parent] = vertex;
}
nodes[vertex].parent = grandparent;
nodes[vertex].child[direction ^ 1] = parent;
nodes[parent].parent = vertex;
nodes[parent].child[direction] = middle;
if (middle != -1) {
nodes[middle].parent = parent;
}
pull(parent);
pull(vertex);
}
void splay(int vertex) {
splay_stack.clear();
splay_stack.push_back(vertex);
for (int current = vertex; !is_auxiliary_root(current);) {
current = nodes[current].parent;
splay_stack.push_back(current);
}
for (auto iterator = splay_stack.rbegin(); iterator != splay_stack.rend();
++iterator) {
push(*iterator);
}
while (!is_auxiliary_root(vertex)) {
int parent = nodes[vertex].parent;
int grandparent = nodes[parent].parent;
if (!is_auxiliary_root(parent)) {
bool vertex_right = nodes[parent].child[1] == vertex;
bool parent_right = nodes[grandparent].child[1] == parent;
rotate(vertex_right == parent_right ? parent : vertex);
}
rotate(vertex);
}
}
int access(int vertex) {
int last = -1;
for (int current = vertex; current != -1;) {
splay(current);
int path_parent = nodes[current].parent;
nodes[current].child[1] = last;
if (last != -1) {
nodes[last].parent = current;
}
pull(current);
last = current;
current = path_parent;
}
splay(vertex);
return last;
}
void make_root(int vertex) {
access(vertex);
apply_reverse(vertex);
}
int find_root(int vertex) {
access(vertex);
push(vertex);
while (nodes[vertex].child[0] != -1) {
vertex = nodes[vertex].child[0];
push(vertex);
}
splay(vertex);
return vertex;
}
};
} // namespace noya
namespace noya {
namespace incremental_msf_detail {
template <class Weight> struct maximum_edge_monoid {
using value_type = std::pair<Weight, int>;
static value_type unit() {
return {std::numeric_limits<Weight>::lowest(), -1};
}
static value_type op(const value_type &left, const value_type &right) {
return std::max(left, right);
}
};
} // namespace incremental_msf_detail
/// @brief Maintain the unique minimum spanning forest under edge insertions.
/// Represent every selected edge by an extra Link-Cut Tree vertex carrying
/// (weight,id), while original vertices carry minus infinity. A cycle-forming
/// insertion exposes its endpoint path: the heaviest selected edge is replaced
/// exactly when it is heavier. Removed edge vertices are reused, so at most
/// n-1 extra nodes are needed even for an arbitrarily long insertion stream.
template <class Weight> class incremental_minimum_spanning_forest {
using monoid = incremental_msf_detail::maximum_edge_monoid<Weight>;
using value_type = typename monoid::value_type;
public:
explicit incremental_minimum_spanning_forest(int n) : vertex_count_(n) {
assert(n >= 0);
forest_.build(std::vector<value_type>(
std::size_t(n) + std::size_t(std::max(0, n - 1)), monoid::unit()));
endpoints_.resize(std::size_t(std::max(0, n - 1)));
}
/// @brief Insert an edge with a globally unique weight and ID. Return -1
/// when it increases the forest size; otherwise return the removed edge ID,
/// which equals id itself when the new edge is rejected.
int add_edge(int first, int second, Weight weight, int id) {
assert(0 <= first && first < vertex_count_);
assert(0 <= second && second < vertex_count_);
if (!forest_.connected(first, second)) {
assert(used_slots_ < std::max(0, vertex_count_ - 1));
install(used_slots_++, first, second, weight, id);
return -1;
}
auto [maximum_weight, maximum_id] =
forest_.path_product(first, second);
if (weight > maximum_weight) {
return id;
}
int slot = id_to_slot_[maximum_id];
auto [old_first, old_second] = endpoints_[slot];
int edge_vertex = vertex_count_ + slot;
bool cut_first = forest_.cut(edge_vertex, old_first);
bool cut_second = forest_.cut(edge_vertex, old_second);
assert(cut_first && cut_second);
install(slot, first, second, weight, id);
return maximum_id;
}
private:
int vertex_count_ = 0;
int used_slots_ = 0;
link_cut_tree<monoid> forest_;
std::vector<std::pair<int, int>> endpoints_;
std::vector<int> id_to_slot_;
void install(int slot, int first, int second, Weight weight, int id) {
assert(id >= 0);
if (int(id_to_slot_.size()) <= id) {
id_to_slot_.resize(id + 1, -1);
}
id_to_slot_[id] = slot;
endpoints_[slot] = {first, second};
int edge_vertex = vertex_count_ + slot;
forest_.set(edge_vertex, {weight, id});
bool linked_first = forest_.link(first, edge_vertex);
bool linked_second = forest_.link(second, edge_vertex);
assert(linked_first && linked_second);
}
};
} // namespace noya