rooted_tree_isomorphism.hpp¶
按完整孩子类型签名给根树精确编号，同一分类器跨次复用类型表；共用签名缓冲区、缓存叶子并避免重复查表，不使用概率哈希。
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.
AC 记录：rooted_tree_isomorphism_classification。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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
// NOYA_ROOTED_TREE_ISOMORPHISM_HPP
#ifndef NOYA_ROOTED_TREE_ISOMORPHISM_HPP
#define NOYA_ROOTED_TREE_ISOMORPHISM_HPP 1
/// @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
#endif // NOYA_ROOTED_TREE_ISOMORPHISM_HPP
/// @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
// NOYA_ROOTED_TREE_ISOMORPHISM_HPP