给定两棵无根树，判断它们是否同构——即是否存在一种节点重标号方式，使得两棵树的边集完全相同。树中节点仅通过编号区分，同构判断不考虑节点编号，只关心拓扑结构。
题目
树的同构判定
给定两棵无根树，判断它们是否同构。
任务要求
- 从标准输入读入两棵树的结构和边信息；
- 使用重心 + 规范编码的方法判定同构；
- 输出判定结果。
输入格式
- 第一行：一个整数
- 接下来
- 接下来一行：一个整数
- 接下来
输出格式
- 若两棵树同构，输出
ISOMORPHIC； - 若不同构，输出
NON-ISOMORPHIC。
数据范围与限制
| 项目 | 范围 |
|---|---|
| 节点数 | |
| 时间复杂度要求 | |
| 额外空间限制 |
关于编码方式
本题允许使用括号串编码（如 (())）或数值哈希编码（如整数 ID）来表示子树的规范形式。括号串编码直观易懂但可能占用较大内存；数值哈希编码空间效率更高，但需要处理哈希冲突。题解中给出括号串编码的参考实现，你可根据喜好选择任意一种正确的方式。
样例
样例输入 1
input
3
1 2
2 3
3
1 2
1 3样例输出 1
output
NON-ISOMORPHIC样例解释 1
第一棵树是链
第二棵树是星形
等等，这两棵树实际上是同构的！让我重新设计样例...
实际上链 1-2-3 和星形 1-2,1-3 都是 3 个节点的树，且每个节点度数为 (1,2,1)。它们同构。让我换一个不同构的例子。
样例输入 1（修正）
input
4
1 2
2 3
3 4
4
1 2
1 3
1 4样例输出 1（修正）
output
NON-ISOMORPHIC样例解释 1（修正）
第一棵树是链
第二棵树是星形，节点 1 连接 2,3,4（最大度数为 3）。
结构不同，不同构。
样例输入 2
input
4
1 2
2 3
2 4
4
1 3
3 2
3 4样例输出 2
output
ISOMORPHIC样例解释 2
两棵树都是"一个中心节点度数为 3，三个叶子"的星形结构，只是节点编号不同，因此同构。
如何验证
先安装 Node.js、pnpm 和支持 C++17 的编译器。GNU Make 是首选入口，但不是强制依赖。
powershell
# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make scoreWindows 没有安装 Make 时，在仓库根目录使用完全相同的评分内核：
powershell
pnpm lab:doctor -- labs/chapter-04/exercise/E-04-20-tree-isomorphism
pnpm lab:run -- labs/chapter-04/exercise/E-04-20-tree-isomorphism
pnpm lab:run -- labs/chapter-04/exercise/E-04-20-tree-isomorphism --case 001-sample
pnpm lab:score -- labs/chapter-04/exercise/E-04-20-tree-isomorphismmake run 在答案尚未全对时仍正常返回，避免 Make 把学习结果显示成工具故障；make score 是严格入口，只有 100 分才返回成功。标准输出参与判题，调试信息请写入标准错误。
题解
点击查看题解
思路
使用重心 + 规范编码的方法。
核心定理：两棵同构的无根树，其重心集合必然同构。因此只需以重心为根进行编码比较。
求重心：
- 一次 DFS 计算每个节点的子树大小
- 删除节点
- 重心：使上述最大值最小的节点。树的重心要么有 1 个，要么有 2 个相邻节点。
规范编码（以某节点为根）：
- 叶子节点：返回
"()"； - 非叶子节点：递归计算所有子树的编码，按字典序排序后拼接，再用
"(" + 拼接结果 + ")"包裹。
同构判断：
- 树 1 的重心集合产生编码集合
- 树 2 的重心集合产生编码集合
- 若
ISOMORPHIC；否则NON-ISOMORPHIC。
算法步骤
- 分别读取两棵树的边信息；
- 对每棵树： a. 求重心（1 个或 2 个）； b. 对每个重心，递归计算规范编码；
- 比较编码集合，输出结果。
复杂度分析
- 时间复杂度：
- 空间复杂度：
边界注意
- 两棵树节点数不同 → 直接不同构；
- 一棵树有 1 个重心，另一棵有 2 个 → 不同构；
- 编码比较时大小写严格匹配输出格式。
点击查看参考代码
cpp
#include <bits/stdc++.h>
using namespace std;
string encode(int u, int p, const vector<vector<int>>& adj) {
vector<string> childCodes;
for (int v : adj[u]) {
if (v == p) continue;
childCodes.push_back(encode(v, u, adj));
}
sort(childCodes.begin(), childCodes.end());
return "(" + accumulate(childCodes.begin(), childCodes.end(), string("")) + ")";
}
vector<int> findCentroids(int n, const vector<vector<int>>& adj) {
vector<int> sz(n + 1, 0);
function<void(int, int)> dfs = [&](int%20u,%20int%20p) {
sz[u] = 1;
for (int v : adj[u]) {
if (v == p) continue;
dfs(v, u);
sz[u] += sz[v];
}
};
dfs(1, 0);
vector<int> cents;
int minMax = n;
function<void(int, int)> dfs2 = [&](int%20u,%20int%20p) {
int mx = n - sz[u];
for (int v : adj[u]) {
if (v == p) continue;
mx = max(mx, sz[v]);
}
if (mx < minMax) {
minMax = mx;
cents = {u};
} else if (mx == minMax) {
cents.push_back(u);
}
for (int v : adj[u]) {
if (v == p) continue;
dfs2(v, u);
}
};
dfs2(1, 0);
return cents;
}
set<string> getCodes(int n, const vector<vector<int>>& adj) {
auto cents = findCentroids(n, adj);
set<string> codes;
for (int c : cents) {
codes.insert(encode(c, 0, adj));
}
return codes;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n1;
if (!(cin >> n1)) return 0;
vector<vector<int>> adj1(n1 + 1);
for (int i = 0; i < n1 - 1; ++i) {
int u, v;
cin >> u >> v;
adj1[u].push_back(v);
adj1[v].push_back(u);
}
int n2;
cin >> n2;
vector<vector<int>> adj2(n2 + 1);
for (int i = 0; i < n2 - 1; ++i) {
int u, v;
cin >> u >> v;
adj2[u].push_back(v);
adj2[v].push_back(u);
}
if (n1 != n2) {
cout << "NON-ISOMORPHIC\n";
return 0;
}
auto codes1 = getCodes(n1, adj1);
auto codes2 = getCodes(n2, adj2);
for (const auto& s : codes1) {
if (codes2.count(s)) {
cout << "ISOMORPHIC\n";
return 0;
}
}
cout << "NON-ISOMORPHIC\n";
return 0;
}