potentialized_dsu.hpp¶
维护带势能差的并查集，支持加入两点差值约束并查询相对势能；适合加权并查集模型。
Complexity: Time: Amortized O(alpha(n)) find/merge/difference. Space: O(n).
AC 记录：unionfind_with_potential。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: Amortized O(alpha(n)) find/merge/difference.
/// Space: O(n).
#include <cassert>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
/// @brief Weighted union-find over an additive group.
/// merge(a, b, w) enforces potential(b) - potential(a) = w.
template <class T> struct potentialized_dsu {
std::vector<int> p;
std::vector<T> w;
potentialized_dsu() = default;
explicit potentialized_dsu(int n) { build(n); }
/// @brief Reset to n singleton components with zero potentials.
void build(int n) {
assert(n >= 0);
p.assign(n, -1);
w.assign(n, T{});
}
/// @brief Return the representative of x with path compression.
int leader(int x) {
assert(0 <= x && x < int(p.size()));
if (p[x] < 0) {
return x;
}
int fa = p[x];
int rt = leader(fa);
w[x] += w[fa];
return p[x] = rt;
}
/// @brief Return potential(x) relative to its component representative.
T potential(int x) {
leader(x);
return w[x];
}
/// @brief Return whether a and b are in the same component.
bool same(int a, int b) { return leader(a) == leader(b); }
/// @brief Return the size of the component containing x.
int size(int x) { return -p[leader(x)]; }
/// @brief Return potential(b) - potential(a), or nullopt if disconnected.
std::optional<T> difference(int a, int b) {
if (!same(a, b)) {
return std::nullopt;
}
return potential(b) - potential(a);
}
/// @brief Add a potential constraint; return false only if it contradicts
/// existing constraints.
bool merge(int a, int b, T dif) {
T wa = potential(a);
T wb = potential(b);
int ra = leader(a);
int rb = leader(b);
if (ra == rb) {
return wb - wa == dif;
}
T dw = dif + wa - wb;
if (-p[ra] < -p[rb]) {
std::swap(ra, rb);
dw = -dw;
}
p[ra] += p[rb];
p[rb] = ra;
w[rb] = dw;
return true;
}
};
} // namespace noya
#ifndef NOYA_POTENTIALIZED_DSU_HPP
#define NOYA_POTENTIALIZED_DSU_HPP 1
/// @complexity Time: Amortized O(alpha(n)) find/merge/difference.
/// Space: O(n).
#include <cassert>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
/// @brief Weighted union-find over an additive group.
/// merge(a, b, w) enforces potential(b) - potential(a) = w.
template <class T> struct potentialized_dsu {
std::vector<int> p;
std::vector<T> w;
potentialized_dsu() = default;
explicit potentialized_dsu(int n) { build(n); }
/// @brief Reset to n singleton components with zero potentials.
void build(int n) {
assert(n >= 0);
p.assign(n, -1);
w.assign(n, T{});
}
/// @brief Return the representative of x with path compression.
int leader(int x) {
assert(0 <= x && x < int(p.size()));
if (p[x] < 0) {
return x;
}
int fa = p[x];
int rt = leader(fa);
w[x] += w[fa];
return p[x] = rt;
}
/// @brief Return potential(x) relative to its component representative.
T potential(int x) {
leader(x);
return w[x];
}
/// @brief Return whether a and b are in the same component.
bool same(int a, int b) { return leader(a) == leader(b); }
/// @brief Return the size of the component containing x.
int size(int x) { return -p[leader(x)]; }
/// @brief Return potential(b) - potential(a), or nullopt if disconnected.
std::optional<T> difference(int a, int b) {
if (!same(a, b)) {
return std::nullopt;
}
return potential(b) - potential(a);
}
/// @brief Add a potential constraint; return false only if it contradicts
/// existing constraints.
bool merge(int a, int b, T dif) {
T wa = potential(a);
T wb = potential(b);
int ra = leader(a);
int rb = leader(b);
if (ra == rb) {
return wb - wa == dif;
}
T dw = dif + wa - wb;
if (-p[ra] < -p[rb]) {
std::swap(ra, rb);
dw = -dw;
}
p[ra] += p[rb];
p[rb] = ra;
w[rb] = dw;
return true;
}
};
} // namespace noya
#endif // NOYA_POTENTIALIZED_DSU_HPP
#include <cassert>
#include <optional>
#include <utility>
#include <vector>
/// @complexity Time: Amortized O(alpha(n)) find/merge/difference.
/// Space: O(n).
namespace noya {
/// @brief Weighted union-find over an additive group.
/// merge(a, b, w) enforces potential(b) - potential(a) = w.
template <class T> struct potentialized_dsu {
std::vector<int> p;
std::vector<T> w;
potentialized_dsu() = default;
explicit potentialized_dsu(int n) { build(n); }
/// @brief Reset to n singleton components with zero potentials.
void build(int n) {
assert(n >= 0);
p.assign(n, -1);
w.assign(n, T{});
}
/// @brief Return the representative of x with path compression.
int leader(int x) {
assert(0 <= x && x < int(p.size()));
if (p[x] < 0) {
return x;
}
int fa = p[x];
int rt = leader(fa);
w[x] += w[fa];
return p[x] = rt;
}
/// @brief Return potential(x) relative to its component representative.
T potential(int x) {
leader(x);
return w[x];
}
/// @brief Return whether a and b are in the same component.
bool same(int a, int b) { return leader(a) == leader(b); }
/// @brief Return the size of the component containing x.
int size(int x) { return -p[leader(x)]; }
/// @brief Return potential(b) - potential(a), or nullopt if disconnected.
std::optional<T> difference(int a, int b) {
if (!same(a, b)) {
return std::nullopt;
}
return potential(b) - potential(a);
}
/// @brief Add a potential constraint; return false only if it contradicts
/// existing constraints.
bool merge(int a, int b, T dif) {
T wa = potential(a);
T wb = potential(b);
int ra = leader(a);
int rb = leader(b);
if (ra == rb) {
return wb - wa == dif;
}
T dw = dif + wa - wb;
if (-p[ra] < -p[rb]) {
std::swap(ra, rb);
dw = -dw;
}
p[ra] += p[rb];
p[rb] = ra;
w[rb] = dw;
return true;
}
};
} // namespace noya