Tree Isomorphism (AHU)
O(n log n)Canonical ids for rooted trees: a node's id is determined by the sorted multiset of its children's ids, interned in a map. Two rooted trees are isomorphic exactly when their root ids match. For unrooted trees, root each tree at its center(s) and compare the resulting id sets.
// use it on
CSES: Tree Isomorphism I ↗
Decide whether two rooted trees are isomorphic: compute tree_id of both roots against a shared canon map and compare.
// the code
// share one canon map across all trees being compared
map<vector<int>, int> canon;
int tree_id(int u, int p, vector<vector<int>>& adj) {
vector<int> childIds;
for (int v : adj[u])
if (v != p) childIds.push_back(tree_id(v, u, adj));
sort(childIds.begin(), childIds.end());
auto it = canon.find(childIds);
if (it == canon.end())
it = canon.emplace(childIds, (int)canon.size()).first;
return it->second;
}
// unrooted trees: root at the center(s) (1 or 2 middle vertices)
vector<int> tree_centers(vector<vector<int>>& adj) {
int n = adj.size(), left = n;
vector<int> deg(n);
vector<bool> removed(n, false);
queue<int> q;
for (int u = 0; u < n; u++) {
deg[u] = adj[u].size();
if (deg[u] <= 1) q.push(u);
}
while (left > 2) {
int layer = q.size();
left -= layer;
while (layer--) {
int u = q.front(); q.pop();
removed[u] = true;
for (int v : adj[u])
if (!removed[v] && --deg[v] == 1) q.push(v);
}
}
vector<int> centers;
while (!q.empty()) { centers.push_back(q.front()); q.pop(); }
return centers;
}
// isomorphic (unrooted) iff the sorted center-id lists are equal