tree_enumeration.hpp¶
逐棵枚举有标号无根树，或每种无标号树形只取一棵；在回调中检查直径、度数等条件即可筛选，适合小规模暴力和对拍。
Complexity: Time: labeled \(O(n)\) per tree; unlabeled tries \((k - 1) t [k - 1]\) candidates at each size \(k\), with \(k\) rooted-isomorphism calls each. Space: labeled \(O(n)\); unlabeled \(O(n^{2} t [n])\), where \(t [k]\) counts tree shapes.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: labeled O(n) per tree; unlabeled tries
/// (k-1) t[k-1] candidates at each size k, with k rooted-isomorphism calls each.
/// Space: labeled O(n); unlabeled O(n^2 t[n]), where t[k] counts tree shapes.
#include "noya/graph/prufer_code.hpp"
#include "noya/graph/rooted_tree_isomorphism.hpp"
#include <algorithm>
#include <cassert>
#include <set>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
namespace internal {
template <class F, class T>
bool visit_tree(F &f, const T &es) {
if constexpr (std::is_void_v<decltype(f(es))>) {
f(es);
return true;
} else {
return f(es);
}
}
} // namespace internal
/// @brief Enumerate unrooted labeled trees on [0,n), in Prüfer-code order.
/// Call f(const vector<pair<int,int>>& edges); copy edges to keep a tree.
/// A void callback continues, false stops; return whether enumeration completed.
/// Require n>=0: n=0 emits nothing, n=1 emits one empty edge list.
/// For n>=2 there are n^(n-2) trees. Callback time is additional.
template <class F>
bool enumerate_labeled_trees(int n, F &&f) {
assert(n >= 0);
if (n == 0) return true;
if (n == 1) {
const std::vector<std::pair<int, int>> es;
return internal::visit_tree(f, es);
}
std::vector<int> s(n - 2);
while (true) {
if (!internal::visit_tree(f, prufer_decode(s))) return false;
int i = int(s.size()) - 1;
while (i >= 0 && s[i] == n - 1) s[i--] = 0;
if (i < 0) return true;
++s[i];
}
}
/// @brief Enumerate unrooted unlabeled trees, one representative per shape.
/// Callback and n=0/1 behavior match enumerate_labeled_trees. Representative
/// vertices still use [0,n) as array indices; renumberings are not new trees.
/// Grow each smaller shape by attaching one leaf, then deduplicate exactly.
/// The shared isomorphism table assigns equal IDs to equal rooted shapes.
/// Taking the minimum ID over all roots makes the key independent of the root.
/// This small-instance implementation keeps earlier shapes and a dedup table;
/// stopping the callback does not avoid generating sizes below n.
template <class F>
bool enumerate_unlabeled_trees(int n, F &&f) {
assert(n >= 0);
if (n <= 1) return enumerate_labeled_trees(n, f);
using edges = std::vector<std::pair<int, int>>;
std::vector<edges> cur(1);
for (int k = 2; k <= n; ++k) {
tree_isomorphism iso;
std::set<int> seen;
std::vector<edges> nxt;
for (const auto &base : cur) {
for (int v = 0; v < k - 1; ++v) {
auto es = base;
es.emplace_back(v, k - 1);
std::vector<std::vector<int>> g(k);
for (auto [a, b] : es) {
g[a].push_back(b);
g[b].push_back(a);
}
int key = iso.solve(g, 0)[0];
for (int rt = 1; rt < k; ++rt)
key = std::min(key, iso.solve(g, rt)[rt]);
if (!seen.insert(key).second) continue;
if (k == n) {
if (!internal::visit_tree(f, es)) return false;
} else {
nxt.push_back(std::move(es));
}
}
}
cur = std::move(nxt);
}
return true;
}
} // namespace noya
// NOYA_TREE_ENUMERATION_HPP
#ifndef NOYA_TREE_ENUMERATION_HPP
#define NOYA_TREE_ENUMERATION_HPP 1
/// @complexity Time: labeled O(n) per tree; unlabeled tries
/// (k-1) t[k-1] candidates at each size k, with k rooted-isomorphism calls each.
/// Space: labeled O(n); unlabeled O(n^2 t[n]), where t[k] counts tree shapes.
#include "noya/graph/prufer_code.hpp"
#include "noya/graph/rooted_tree_isomorphism.hpp"
#include <algorithm>
#include <cassert>
#include <set>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
namespace internal {
template <class F, class T>
bool visit_tree(F &f, const T &es) {
if constexpr (std::is_void_v<decltype(f(es))>) {
f(es);
return true;
} else {
return f(es);
}
}
} // namespace internal
/// @brief Enumerate unrooted labeled trees on [0,n), in Prüfer-code order.
/// Call f(const vector<pair<int,int>>& edges); copy edges to keep a tree.
/// A void callback continues, false stops; return whether enumeration completed.
/// Require n>=0: n=0 emits nothing, n=1 emits one empty edge list.
/// For n>=2 there are n^(n-2) trees. Callback time is additional.
template <class F>
bool enumerate_labeled_trees(int n, F &&f) {
assert(n >= 0);
if (n == 0) return true;
if (n == 1) {
const std::vector<std::pair<int, int>> es;
return internal::visit_tree(f, es);
}
std::vector<int> s(n - 2);
while (true) {
if (!internal::visit_tree(f, prufer_decode(s))) return false;
int i = int(s.size()) - 1;
while (i >= 0 && s[i] == n - 1) s[i--] = 0;
if (i < 0) return true;
++s[i];
}
}
/// @brief Enumerate unrooted unlabeled trees, one representative per shape.
/// Callback and n=0/1 behavior match enumerate_labeled_trees. Representative
/// vertices still use [0,n) as array indices; renumberings are not new trees.
/// Grow each smaller shape by attaching one leaf, then deduplicate exactly.
/// The shared isomorphism table assigns equal IDs to equal rooted shapes.
/// Taking the minimum ID over all roots makes the key independent of the root.
/// This small-instance implementation keeps earlier shapes and a dedup table;
/// stopping the callback does not avoid generating sizes below n.
template <class F>
bool enumerate_unlabeled_trees(int n, F &&f) {
assert(n >= 0);
if (n <= 1) return enumerate_labeled_trees(n, f);
using edges = std::vector<std::pair<int, int>>;
std::vector<edges> cur(1);
for (int k = 2; k <= n; ++k) {
tree_isomorphism iso;
std::set<int> seen;
std::vector<edges> nxt;
for (const auto &base : cur) {
for (int v = 0; v < k - 1; ++v) {
auto es = base;
es.emplace_back(v, k - 1);
std::vector<std::vector<int>> g(k);
for (auto [a, b] : es) {
g[a].push_back(b);
g[b].push_back(a);
}
int key = iso.solve(g, 0)[0];
for (int rt = 1; rt < k; ++rt)
key = std::min(key, iso.solve(g, rt)[rt]);
if (!seen.insert(key).second) continue;
if (k == n) {
if (!internal::visit_tree(f, es)) return false;
} else {
nxt.push_back(std::move(es));
}
}
}
cur = std::move(nxt);
}
return true;
}
} // namespace noya
#endif // NOYA_TREE_ENUMERATION_HPP
/// @complexity Time: labeled O(n) per tree; unlabeled tries
/// (k-1) t[k-1] candidates at each size k, with k rooted-isomorphism calls each.
/// Space: labeled O(n); unlabeled O(n^2 t[n]), where t[k] counts tree shapes.
/// @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
/// @complexity Time: O(n log(n+M+1)), with M previously interned types.
/// Space: O(n+M+L), with L integers in retained keys; O(n) recursion depth.
#include <algorithm>
#include <cassert>
#include <map>
#include <vector>
namespace noya {
/// @brief Intern exact rooted-subtree types, shared across calls on this object.
struct tree_isomorphism {
std::map<std::vector<int>, int> mp;
int cnt = 0;
/// @brief Label every subtree rooted at rt, ignoring child order.
/// Accept an undirected tree or its outward child lists; leave g unchanged.
/// Compare IDs only within the same type table. Empty input changes nothing.
std::vector<int> solve(const std::vector<std::vector<int>> &g,
const int rt = 0) {
int N = int(g.size());
std::vector<int> ans(N);
if (N == 0) return ans;
assert(0 <= rt && rt < N);
// The first postorder vertex is a leaf, so its ID is unchanged.
auto [leaf, inserted] = mp.try_emplace(std::vector<int>{}, cnt);
cnt += inserted;
int leaf_id = leaf->second;
std::vector<int> ch;
auto dfs = [&](auto &self, int u, int fa) -> int {
int children = 0;
for (int v : g[u]) {
assert(0 <= v && v < N);
if (v != fa) {
self(self, v, u);
++children;
}
}
if (children == 0) return ans[u] = leaf_id;
// Finish children before reusing this scratch; copy only new keys.
ch.clear();
ch.reserve(children);
for (int v : g[u]) if (v != fa) ch.push_back(ans[v]);
if (!std::is_sorted(ch.begin(), ch.end()))
std::sort(ch.begin(), ch.end());
auto size = mp.size();
auto it = mp.try_emplace(mp.end(), ch, cnt);
cnt += mp.size() != size;
return ans[u] = it->second;
};
dfs(dfs, rt, -1);
return ans;
}
};
} // namespace noya
#include <algorithm>
#include <cassert>
#include <set>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
namespace internal {
template <class F, class T>
bool visit_tree(F &f, const T &es) {
if constexpr (std::is_void_v<decltype(f(es))>) {
f(es);
return true;
} else {
return f(es);
}
}
} // namespace internal
/// @brief Enumerate unrooted labeled trees on [0,n), in Prüfer-code order.
/// Call f(const vector<pair<int,int>>& edges); copy edges to keep a tree.
/// A void callback continues, false stops; return whether enumeration completed.
/// Require n>=0: n=0 emits nothing, n=1 emits one empty edge list.
/// For n>=2 there are n^(n-2) trees. Callback time is additional.
template <class F>
bool enumerate_labeled_trees(int n, F &&f) {
assert(n >= 0);
if (n == 0) return true;
if (n == 1) {
const std::vector<std::pair<int, int>> es;
return internal::visit_tree(f, es);
}
std::vector<int> s(n - 2);
while (true) {
if (!internal::visit_tree(f, prufer_decode(s))) return false;
int i = int(s.size()) - 1;
while (i >= 0 && s[i] == n - 1) s[i--] = 0;
if (i < 0) return true;
++s[i];
}
}
/// @brief Enumerate unrooted unlabeled trees, one representative per shape.
/// Callback and n=0/1 behavior match enumerate_labeled_trees. Representative
/// vertices still use [0,n) as array indices; renumberings are not new trees.
/// Grow each smaller shape by attaching one leaf, then deduplicate exactly.
/// The shared isomorphism table assigns equal IDs to equal rooted shapes.
/// Taking the minimum ID over all roots makes the key independent of the root.
/// This small-instance implementation keeps earlier shapes and a dedup table;
/// stopping the callback does not avoid generating sizes below n.
template <class F>
bool enumerate_unlabeled_trees(int n, F &&f) {
assert(n >= 0);
if (n <= 1) return enumerate_labeled_trees(n, f);
using edges = std::vector<std::pair<int, int>>;
std::vector<edges> cur(1);
for (int k = 2; k <= n; ++k) {
tree_isomorphism iso;
std::set<int> seen;
std::vector<edges> nxt;
for (const auto &base : cur) {
for (int v = 0; v < k - 1; ++v) {
auto es = base;
es.emplace_back(v, k - 1);
std::vector<std::vector<int>> g(k);
for (auto [a, b] : es) {
g[a].push_back(b);
g[b].push_back(a);
}
int key = iso.solve(g, 0)[0];
for (int rt = 1; rt < k; ++rt)
key = std::min(key, iso.solve(g, rt)[rt]);
if (!seen.insert(key).second) continue;
if (k == n) {
if (!internal::visit_tree(f, es)) return false;
} else {
nxt.push_back(std::move(es));
}
}
}
cur = std::move(nxt);
}
return true;
}
} // namespace noya
// NOYA_TREE_ENUMERATION_HPP