prufer_code.hpp¶
用单调叶子指针在线性时间内编解码 Prüfer 序列；编码以度数和邻居异或值代替邻接表，保持最小叶子顺序；枚举所有树使用 tree_enumeration。
Complexity: Time: \(O(n)\) for encoding and decoding. Space: \(O(n)\).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n) for encoding and decoding.
/// Space: O(n).
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
/// @brief Encode a labeled tree on vertices [0, n) as its Prüfer sequence in
/// O(n), always removing the smallest current leaf. Require a tree and n>=2.
inline std::vector<int>
prufer_encode(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 2);
assert(int(es.size()) == n - 1);
if (n <= 2) {
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
assert(a != b);
}
return {};
}
std::vector<int> deg(n), neighbor(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
assert(a != b);
neighbor[a] ^= b;
neighbor[b] ^= a;
deg[a]++;
deg[b]++;
}
int ptr = 0;
while (deg[ptr] != 1) ++ptr;
int leaf = ptr;
std::vector<int> s;
s.reserve(n - 2);
for (int stp = 0; stp < n - 2; stp++) {
int v = neighbor[leaf];
s.push_back(v);
deg[leaf] = 0;
neighbor[v] ^= leaf;
// Only v can become a leaf below the monotone scan pointer.
if (--deg[v] == 1 && v < ptr) {
leaf = v;
} else {
while (deg[++ptr] != 1) {}
leaf = ptr;
}
}
return s;
}
/// @brief Decode a Prüfer sequence over labels [0, s.size()+2) into a tree
/// in O(n), returning edges in leaf-removal order, then the last pair ascending.
inline std::vector<std::pair<int, int>>
prufer_decode(const std::vector<int> &s) {
const int n = int(s.size()) + 2;
std::vector<int> deg(n, 1);
for (int u : s) {
assert(0 <= u && u < n);
deg[u]++;
}
int ptr = 0;
while (deg[ptr] != 1) ++ptr;
int leaf = ptr;
std::vector<std::pair<int, int>> es;
es.reserve(n - 1);
for (int u : s) {
es.emplace_back(leaf, u);
deg[leaf] = 0;
if (--deg[u] == 1 && u < ptr) {
leaf = u;
} else {
while (deg[++ptr] != 1) {}
leaf = ptr;
}
}
// The largest label survives every smallest-leaf removal.
es.emplace_back(leaf, n - 1);
return es;
}
} // namespace noya
// NOYA_PRUFER_CODE_HPP
#ifndef NOYA_PRUFER_CODE_HPP
#define NOYA_PRUFER_CODE_HPP 1
/// @complexity Time: O(n) for encoding and decoding.
/// Space: O(n).
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
/// @brief Encode a labeled tree on vertices [0, n) as its Prüfer sequence in
/// O(n), always removing the smallest current leaf. Require a tree and n>=2.
inline std::vector<int>
prufer_encode(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 2);
assert(int(es.size()) == n - 1);
if (n <= 2) {
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
assert(a != b);
}
return {};
}
std::vector<int> deg(n), neighbor(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
assert(a != b);
neighbor[a] ^= b;
neighbor[b] ^= a;
deg[a]++;
deg[b]++;
}
int ptr = 0;
while (deg[ptr] != 1) ++ptr;
int leaf = ptr;
std::vector<int> s;
s.reserve(n - 2);
for (int stp = 0; stp < n - 2; stp++) {
int v = neighbor[leaf];
s.push_back(v);
deg[leaf] = 0;
neighbor[v] ^= leaf;
// Only v can become a leaf below the monotone scan pointer.
if (--deg[v] == 1 && v < ptr) {
leaf = v;
} else {
while (deg[++ptr] != 1) {}
leaf = ptr;
}
}
return s;
}
/// @brief Decode a Prüfer sequence over labels [0, s.size()+2) into a tree
/// in O(n), returning edges in leaf-removal order, then the last pair ascending.
inline std::vector<std::pair<int, int>>
prufer_decode(const std::vector<int> &s) {
const int n = int(s.size()) + 2;
std::vector<int> deg(n, 1);
for (int u : s) {
assert(0 <= u && u < n);
deg[u]++;
}
int ptr = 0;
while (deg[ptr] != 1) ++ptr;
int leaf = ptr;
std::vector<std::pair<int, int>> es;
es.reserve(n - 1);
for (int u : s) {
es.emplace_back(leaf, u);
deg[leaf] = 0;
if (--deg[u] == 1 && u < ptr) {
leaf = u;
} else {
while (deg[++ptr] != 1) {}
leaf = ptr;
}
}
// The largest label survives every smallest-leaf removal.
es.emplace_back(leaf, n - 1);
return es;
}
} // namespace noya
#endif // NOYA_PRUFER_CODE_HPP
/// @complexity Time: O(n) for encoding and decoding.
/// Space: O(n).
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
/// @brief Encode a labeled tree on vertices [0, n) as its Prüfer sequence in
/// O(n), always removing the smallest current leaf. Require a tree and n>=2.
inline std::vector<int>
prufer_encode(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 2);
assert(int(es.size()) == n - 1);
if (n <= 2) {
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
assert(a != b);
}
return {};
}
std::vector<int> deg(n), neighbor(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n);
assert(0 <= b && b < n);
assert(a != b);
neighbor[a] ^= b;
neighbor[b] ^= a;
deg[a]++;
deg[b]++;
}
int ptr = 0;
while (deg[ptr] != 1) ++ptr;
int leaf = ptr;
std::vector<int> s;
s.reserve(n - 2);
for (int stp = 0; stp < n - 2; stp++) {
int v = neighbor[leaf];
s.push_back(v);
deg[leaf] = 0;
neighbor[v] ^= leaf;
// Only v can become a leaf below the monotone scan pointer.
if (--deg[v] == 1 && v < ptr) {
leaf = v;
} else {
while (deg[++ptr] != 1) {}
leaf = ptr;
}
}
return s;
}
/// @brief Decode a Prüfer sequence over labels [0, s.size()+2) into a tree
/// in O(n), returning edges in leaf-removal order, then the last pair ascending.
inline std::vector<std::pair<int, int>>
prufer_decode(const std::vector<int> &s) {
const int n = int(s.size()) + 2;
std::vector<int> deg(n, 1);
for (int u : s) {
assert(0 <= u && u < n);
deg[u]++;
}
int ptr = 0;
while (deg[ptr] != 1) ++ptr;
int leaf = ptr;
std::vector<std::pair<int, int>> es;
es.reserve(n - 1);
for (int u : s) {
es.emplace_back(leaf, u);
deg[leaf] = 0;
if (--deg[u] == 1 && u < ptr) {
leaf = u;
} else {
while (deg[++ptr] != 1) {}
leaf = ptr;
}
}
// The largest label survives every smallest-leaf removal.
es.emplace_back(leaf, n - 1);
return es;
}
} // namespace noya
// NOYA_PRUFER_CODE_HPP