rooted_tree_isomorphism.hpp¶
Assign canonical hash labels to rooted subtrees for isomorphism testing.
Verified by rooted_tree_isomorphism_classification.
给有根树分配同构类型编号；用于判断多棵根树是否只差孩子排列，或压缩相同子树结构。
Implementation¶
#ifndef NOYA_ROOTED_TREE_ISOMORPHISM_HPP
#define NOYA_ROOTED_TREE_ISOMORPHISM_HPP 1
/// @complexity Time: O(n log n) from sorting child labels.
/// Space: O(n).
#include <algorithm>
#include <map>
#include <vector>
namespace noya {
/// @brief Assign canonical hash labels to rooted subtrees for isomorphism testing.
struct tree_isomorphism {
std::map<std::vector<int>, int> mp;
int cnt = 0;
/// @brief Compute canonical labels for all nodes of a rooted tree.
/// @return Vector mapping each node to its canonical subtree label.
std::vector<int> solve(const std::vector<std::vector<int>> &g,
const int root = 0) {
int N = int(g.size());
std::vector<int> ans(N);
auto dfs = [&](auto &self, int u, int parent) -> int {
std::vector<int> sons;
for (int v : g[u]) {
if (v != parent) {
sons.push_back(self(self, v, u));
}
}
std::sort(sons.begin(), sons.end());
if (!mp.count(sons))
mp[sons] = cnt++;
return ans[u] = mp[sons];
};
dfs(dfs, root, -1);
return ans;
}
};
} // namespace noya
#endif // NOYA_ROOTED_TREE_ISOMORPHISM_HPP
#include <algorithm>
#include <map>
#include <vector>
/// @complexity Time: O(n log n) from sorting child labels.
/// Space: O(n).
namespace noya {
/// @brief Assign canonical hash labels to rooted subtrees for isomorphism testing.
struct tree_isomorphism {
std::map<std::vector<int>, int> mp;
int cnt = 0;
/// @brief Compute canonical labels for all nodes of a rooted tree.
/// @return Vector mapping each node to its canonical subtree label.
std::vector<int> solve(const std::vector<std::vector<int>> &g,
const int root = 0) {
int N = int(g.size());
std::vector<int> ans(N);
auto dfs = [&](auto &self, int u, int parent) -> int {
std::vector<int> sons;
for (int v : g[u]) {
if (v != parent) {
sons.push_back(self(self, v, u));
}
}
std::sort(sons.begin(), sons.end());
if (!mp.count(sons))
mp[sons] = cnt++;
return ans[u] = mp[sons];
};
dfs(dfs, root, -1);
return ans;
}
};
} // namespace noya