incremental_msf.hpp¶
互异权值的增量最小生成森林，返回替换边 ID；并查集判连通，精简动态树维护路径最大边，固定槽位保证 O(\(n\)) 空间。
Complexity: Time: \(O(n)\) construction, amortized \(O(\log (n + 1))\) per insertion. Space: \(O(n)\), independent of the number of insertions and the edge IDs.
AC 记录：incremental_minimum_spanning_forest。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n) construction, amortized O(log(n+1)) per insertion.
/// Space: O(n), independent of the number of insertions and the edge IDs.
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
namespace incremental_msf_detail {
// Only edge vertices participate in maxima. No numeric sentinel, size or
// ordered/reversed path product is needed for this commutative operation.
template <class Weight> class maximum_path_tree {
struct node {
int ch[2] = {-1, -1}, fa = -1, mx = -1;
bool rev = false;
Weight w{};
};
int vertices;
std::vector<node> tr;
std::vector<int> stack;
bool root(int u) const {
int p = tr[u].fa;
return p == -1 || (tr[p].ch[0] != u && tr[p].ch[1] != u);
}
int better(int a, int b) const {
if (a == -1) return b;
if (b == -1) return a;
return tr[a].w < tr[b].w ? b : a;
}
void pull(int u) {
int best = u < vertices ? -1 : u;
for (int v : tr[u].ch) {
if (v != -1) best = better(best, tr[v].mx);
}
tr[u].mx = best;
}
void reverse(int u) {
if (u == -1) return;
std::swap(tr[u].ch[0], tr[u].ch[1]);
tr[u].rev = !tr[u].rev;
}
void push(int u) {
if (tr[u].rev) {
reverse(tr[u].ch[0]);
reverse(tr[u].ch[1]);
tr[u].rev = false;
}
}
void rotate(int u) {
int p = tr[u].fa, g = tr[p].fa, d = tr[p].ch[1] == u;
int mid = tr[u].ch[d ^ 1];
if (!root(p)) tr[g].ch[tr[g].ch[1] == p] = u;
tr[u].fa = g;
tr[u].ch[d ^ 1] = p;
tr[p].fa = u;
tr[p].ch[d] = mid;
if (mid != -1) tr[mid].fa = p;
pull(p);
}
void splay(int u) {
if (root(u)) {
push(u);
return;
}
stack.clear();
stack.push_back(u);
for (int v = u; !root(v);) {
v = tr[v].fa;
stack.push_back(v);
}
for (auto it = stack.rbegin(); it != stack.rend(); ++it) push(*it);
while (!root(u)) {
int p = tr[u].fa, g = tr[p].fa;
if (!root(p)) {
rotate((tr[p].ch[1] == u) == (tr[g].ch[1] == p) ? p : u);
}
rotate(u);
}
pull(u);
}
void access(int u) {
int last = -1;
for (int v = u; v != -1;) {
splay(v);
int p = tr[v].fa;
tr[v].ch[1] = last;
if (last != -1) tr[last].fa = v;
pull(v);
last = v;
v = p;
}
splay(u);
}
void make_root(int u) {
access(u);
reverse(u);
}
public:
explicit maximum_path_tree(int n) : vertices(n) {
assert(n >= 0);
tr.resize(std::size_t(n) + std::size_t(std::max(0, n - 1)));
stack.reserve(tr.size());
}
// The caller supplies an isolated edge vertex and disconnected endpoints.
void install(int edge, int a, int b, Weight w) {
assert(tr[edge].fa == -1 && tr[edge].ch[0] == -1 &&
tr[edge].ch[1] == -1);
tr[edge] = node{};
tr[edge].w = w;
tr[edge].mx = edge;
make_root(a);
tr[a].fa = edge;
tr[edge].fa = b;
}
void cut(int a, int b) {
make_root(a);
access(b);
assert(tr[b].ch[0] == a && tr[a].ch[1] == -1);
tr[b].ch[0] = -1;
tr[a].fa = -1;
pull(b);
}
int max_path(int a, int b) {
make_root(a);
access(b);
return tr[b].mx;
}
const Weight &weight(int u) const { return tr[u].w; }
};
} // namespace incremental_msf_detail
/// @brief Maintain the unique minimum spanning forest for distinct weights.
/// Selected edges use reusable slots; connectivity only grows, so a DSU
/// avoids dynamic-tree root searches before each path query.
template <class Weight> class incremental_minimum_spanning_forest {
public:
explicit incremental_minimum_spanning_forest(int n)
: n_(n), tr_(n), end(std::max(0, n - 1)),
ids(std::max(0, n - 1)), dsu(n, -1) {
assert(n >= 0);
}
/// @brief Insert an edge with globally unique weight and nonnegative ID.
/// IDs must also be globally unique, but need not be consecutive or ordered.
/// Return -1 when the forest grows; otherwise return the removed ID, or id
/// itself when this edge is rejected. Self-loops are always rejected.
int add_edge(int a, int b, Weight w, int id) {
assert(0 <= a && a < n_ && 0 <= b && b < n_);
assert(id >= 0);
if (a == b) return id;
int x = leader(a), y = leader(b);
if (x != y) {
if (dsu[x] > dsu[y]) std::swap(x, y);
dsu[x] += dsu[y];
dsu[y] = x;
assert(us < std::max(0, n_ - 1));
install(us++, a, b, w, id);
return -1;
}
int edge = tr_.max_path(a, b);
assert(edge >= n_);
if (!(w < tr_.weight(edge))) return id;
int slot = edge - n_, removed = ids[slot];
auto [oa, ob] = end[slot];
tr_.cut(edge, oa);
tr_.cut(edge, ob);
install(slot, a, b, w, id);
return removed;
}
private:
int n_ = 0, us = 0;
incremental_msf_detail::maximum_path_tree<Weight> tr_;
std::vector<std::pair<int, int>> end;
std::vector<int> ids, dsu;
int leader(int u) {
int r = u;
while (dsu[r] >= 0) r = dsu[r];
while (u != r) {
int p = dsu[u];
dsu[u] = r;
u = p;
}
return r;
}
void install(int slot, int a, int b, Weight w, int id) {
ids[slot] = id;
end[slot] = {a, b};
tr_.install(n_ + slot, a, b, w);
}
};
} // namespace noya
// NOYA_INCREMENTAL_MSF_HPP
#ifndef NOYA_INCREMENTAL_MSF_HPP
#define NOYA_INCREMENTAL_MSF_HPP 1
/// @complexity Time: O(n) construction, amortized O(log(n+1)) per insertion.
/// Space: O(n), independent of the number of insertions and the edge IDs.
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
namespace incremental_msf_detail {
// Only edge vertices participate in maxima. No numeric sentinel, size or
// ordered/reversed path product is needed for this commutative operation.
template <class Weight> class maximum_path_tree {
struct node {
int ch[2] = {-1, -1}, fa = -1, mx = -1;
bool rev = false;
Weight w{};
};
int vertices;
std::vector<node> tr;
std::vector<int> stack;
bool root(int u) const {
int p = tr[u].fa;
return p == -1 || (tr[p].ch[0] != u && tr[p].ch[1] != u);
}
int better(int a, int b) const {
if (a == -1) return b;
if (b == -1) return a;
return tr[a].w < tr[b].w ? b : a;
}
void pull(int u) {
int best = u < vertices ? -1 : u;
for (int v : tr[u].ch) {
if (v != -1) best = better(best, tr[v].mx);
}
tr[u].mx = best;
}
void reverse(int u) {
if (u == -1) return;
std::swap(tr[u].ch[0], tr[u].ch[1]);
tr[u].rev = !tr[u].rev;
}
void push(int u) {
if (tr[u].rev) {
reverse(tr[u].ch[0]);
reverse(tr[u].ch[1]);
tr[u].rev = false;
}
}
void rotate(int u) {
int p = tr[u].fa, g = tr[p].fa, d = tr[p].ch[1] == u;
int mid = tr[u].ch[d ^ 1];
if (!root(p)) tr[g].ch[tr[g].ch[1] == p] = u;
tr[u].fa = g;
tr[u].ch[d ^ 1] = p;
tr[p].fa = u;
tr[p].ch[d] = mid;
if (mid != -1) tr[mid].fa = p;
pull(p);
}
void splay(int u) {
if (root(u)) {
push(u);
return;
}
stack.clear();
stack.push_back(u);
for (int v = u; !root(v);) {
v = tr[v].fa;
stack.push_back(v);
}
for (auto it = stack.rbegin(); it != stack.rend(); ++it) push(*it);
while (!root(u)) {
int p = tr[u].fa, g = tr[p].fa;
if (!root(p)) {
rotate((tr[p].ch[1] == u) == (tr[g].ch[1] == p) ? p : u);
}
rotate(u);
}
pull(u);
}
void access(int u) {
int last = -1;
for (int v = u; v != -1;) {
splay(v);
int p = tr[v].fa;
tr[v].ch[1] = last;
if (last != -1) tr[last].fa = v;
pull(v);
last = v;
v = p;
}
splay(u);
}
void make_root(int u) {
access(u);
reverse(u);
}
public:
explicit maximum_path_tree(int n) : vertices(n) {
assert(n >= 0);
tr.resize(std::size_t(n) + std::size_t(std::max(0, n - 1)));
stack.reserve(tr.size());
}
// The caller supplies an isolated edge vertex and disconnected endpoints.
void install(int edge, int a, int b, Weight w) {
assert(tr[edge].fa == -1 && tr[edge].ch[0] == -1 &&
tr[edge].ch[1] == -1);
tr[edge] = node{};
tr[edge].w = w;
tr[edge].mx = edge;
make_root(a);
tr[a].fa = edge;
tr[edge].fa = b;
}
void cut(int a, int b) {
make_root(a);
access(b);
assert(tr[b].ch[0] == a && tr[a].ch[1] == -1);
tr[b].ch[0] = -1;
tr[a].fa = -1;
pull(b);
}
int max_path(int a, int b) {
make_root(a);
access(b);
return tr[b].mx;
}
const Weight &weight(int u) const { return tr[u].w; }
};
} // namespace incremental_msf_detail
/// @brief Maintain the unique minimum spanning forest for distinct weights.
/// Selected edges use reusable slots; connectivity only grows, so a DSU
/// avoids dynamic-tree root searches before each path query.
template <class Weight> class incremental_minimum_spanning_forest {
public:
explicit incremental_minimum_spanning_forest(int n)
: n_(n), tr_(n), end(std::max(0, n - 1)),
ids(std::max(0, n - 1)), dsu(n, -1) {
assert(n >= 0);
}
/// @brief Insert an edge with globally unique weight and nonnegative ID.
/// IDs must also be globally unique, but need not be consecutive or ordered.
/// Return -1 when the forest grows; otherwise return the removed ID, or id
/// itself when this edge is rejected. Self-loops are always rejected.
int add_edge(int a, int b, Weight w, int id) {
assert(0 <= a && a < n_ && 0 <= b && b < n_);
assert(id >= 0);
if (a == b) return id;
int x = leader(a), y = leader(b);
if (x != y) {
if (dsu[x] > dsu[y]) std::swap(x, y);
dsu[x] += dsu[y];
dsu[y] = x;
assert(us < std::max(0, n_ - 1));
install(us++, a, b, w, id);
return -1;
}
int edge = tr_.max_path(a, b);
assert(edge >= n_);
if (!(w < tr_.weight(edge))) return id;
int slot = edge - n_, removed = ids[slot];
auto [oa, ob] = end[slot];
tr_.cut(edge, oa);
tr_.cut(edge, ob);
install(slot, a, b, w, id);
return removed;
}
private:
int n_ = 0, us = 0;
incremental_msf_detail::maximum_path_tree<Weight> tr_;
std::vector<std::pair<int, int>> end;
std::vector<int> ids, dsu;
int leader(int u) {
int r = u;
while (dsu[r] >= 0) r = dsu[r];
while (u != r) {
int p = dsu[u];
dsu[u] = r;
u = p;
}
return r;
}
void install(int slot, int a, int b, Weight w, int id) {
ids[slot] = id;
end[slot] = {a, b};
tr_.install(n_ + slot, a, b, w);
}
};
} // namespace noya
#endif // NOYA_INCREMENTAL_MSF_HPP
/// @complexity Time: O(n) construction, amortized O(log(n+1)) per insertion.
/// Space: O(n), independent of the number of insertions and the edge IDs.
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
namespace incremental_msf_detail {
// Only edge vertices participate in maxima. No numeric sentinel, size or
// ordered/reversed path product is needed for this commutative operation.
template <class Weight> class maximum_path_tree {
struct node {
int ch[2] = {-1, -1}, fa = -1, mx = -1;
bool rev = false;
Weight w{};
};
int vertices;
std::vector<node> tr;
std::vector<int> stack;
bool root(int u) const {
int p = tr[u].fa;
return p == -1 || (tr[p].ch[0] != u && tr[p].ch[1] != u);
}
int better(int a, int b) const {
if (a == -1) return b;
if (b == -1) return a;
return tr[a].w < tr[b].w ? b : a;
}
void pull(int u) {
int best = u < vertices ? -1 : u;
for (int v : tr[u].ch) {
if (v != -1) best = better(best, tr[v].mx);
}
tr[u].mx = best;
}
void reverse(int u) {
if (u == -1) return;
std::swap(tr[u].ch[0], tr[u].ch[1]);
tr[u].rev = !tr[u].rev;
}
void push(int u) {
if (tr[u].rev) {
reverse(tr[u].ch[0]);
reverse(tr[u].ch[1]);
tr[u].rev = false;
}
}
void rotate(int u) {
int p = tr[u].fa, g = tr[p].fa, d = tr[p].ch[1] == u;
int mid = tr[u].ch[d ^ 1];
if (!root(p)) tr[g].ch[tr[g].ch[1] == p] = u;
tr[u].fa = g;
tr[u].ch[d ^ 1] = p;
tr[p].fa = u;
tr[p].ch[d] = mid;
if (mid != -1) tr[mid].fa = p;
pull(p);
}
void splay(int u) {
if (root(u)) {
push(u);
return;
}
stack.clear();
stack.push_back(u);
for (int v = u; !root(v);) {
v = tr[v].fa;
stack.push_back(v);
}
for (auto it = stack.rbegin(); it != stack.rend(); ++it) push(*it);
while (!root(u)) {
int p = tr[u].fa, g = tr[p].fa;
if (!root(p)) {
rotate((tr[p].ch[1] == u) == (tr[g].ch[1] == p) ? p : u);
}
rotate(u);
}
pull(u);
}
void access(int u) {
int last = -1;
for (int v = u; v != -1;) {
splay(v);
int p = tr[v].fa;
tr[v].ch[1] = last;
if (last != -1) tr[last].fa = v;
pull(v);
last = v;
v = p;
}
splay(u);
}
void make_root(int u) {
access(u);
reverse(u);
}
public:
explicit maximum_path_tree(int n) : vertices(n) {
assert(n >= 0);
tr.resize(std::size_t(n) + std::size_t(std::max(0, n - 1)));
stack.reserve(tr.size());
}
// The caller supplies an isolated edge vertex and disconnected endpoints.
void install(int edge, int a, int b, Weight w) {
assert(tr[edge].fa == -1 && tr[edge].ch[0] == -1 &&
tr[edge].ch[1] == -1);
tr[edge] = node{};
tr[edge].w = w;
tr[edge].mx = edge;
make_root(a);
tr[a].fa = edge;
tr[edge].fa = b;
}
void cut(int a, int b) {
make_root(a);
access(b);
assert(tr[b].ch[0] == a && tr[a].ch[1] == -1);
tr[b].ch[0] = -1;
tr[a].fa = -1;
pull(b);
}
int max_path(int a, int b) {
make_root(a);
access(b);
return tr[b].mx;
}
const Weight &weight(int u) const { return tr[u].w; }
};
} // namespace incremental_msf_detail
/// @brief Maintain the unique minimum spanning forest for distinct weights.
/// Selected edges use reusable slots; connectivity only grows, so a DSU
/// avoids dynamic-tree root searches before each path query.
template <class Weight> class incremental_minimum_spanning_forest {
public:
explicit incremental_minimum_spanning_forest(int n)
: n_(n), tr_(n), end(std::max(0, n - 1)),
ids(std::max(0, n - 1)), dsu(n, -1) {
assert(n >= 0);
}
/// @brief Insert an edge with globally unique weight and nonnegative ID.
/// IDs must also be globally unique, but need not be consecutive or ordered.
/// Return -1 when the forest grows; otherwise return the removed ID, or id
/// itself when this edge is rejected. Self-loops are always rejected.
int add_edge(int a, int b, Weight w, int id) {
assert(0 <= a && a < n_ && 0 <= b && b < n_);
assert(id >= 0);
if (a == b) return id;
int x = leader(a), y = leader(b);
if (x != y) {
if (dsu[x] > dsu[y]) std::swap(x, y);
dsu[x] += dsu[y];
dsu[y] = x;
assert(us < std::max(0, n_ - 1));
install(us++, a, b, w, id);
return -1;
}
int edge = tr_.max_path(a, b);
assert(edge >= n_);
if (!(w < tr_.weight(edge))) return id;
int slot = edge - n_, removed = ids[slot];
auto [oa, ob] = end[slot];
tr_.cut(edge, oa);
tr_.cut(edge, ob);
install(slot, a, b, w, id);
return removed;
}
private:
int n_ = 0, us = 0;
incremental_msf_detail::maximum_path_tree<Weight> tr_;
std::vector<std::pair<int, int>> end;
std::vector<int> ids, dsu;
int leader(int u) {
int r = u;
while (dsu[r] >= 0) r = dsu[r];
while (u != r) {
int p = dsu[u];
dsu[u] = r;
u = p;
}
return r;
}
void install(int slot, int a, int b, Weight w, int id) {
ids[slot] = id;
end[slot] = {a, b};
tr_.install(n_ + slot, a, b, w);
}
};
} // namespace noya
// NOYA_INCREMENTAL_MSF_HPP