题目重点：使用按大小合并和路径压缩，处理自环、重复边、断连与单节点，并对照BFS判定。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练n为正整数，边为端点对列表；非法端点报错。单节点无边是树，n=0的空图不在合同内。
- 边列表按实际边计数，不静默去重；自环和重复边都导致不是树。
- 只有布尔结果，无根节点或方向指定。
解题路线
- 树的定义是无向连通无环图。连通树必有n−1条边；反过来，n−1条边单独不够，例如三角环加一个孤立节点。还需要检查无环或检查连通性，两者任选一种配合边数。
- 先验证端点，再检查边数等于n−1。若不等可立即False。代码对非法输入使用异常，故不让边数短路掩盖越界端点，保持API一致性。
- 并查集起始有n个分量，处理边(a,b)时取各自代表。若代表相同，已存在一条a到b路径，再添边便闭环；自环直接命中同代表，重复边第二次也一样。
- 代表不同则合并两个分量，每条成功边恰好减少一个分量。n−1条全部成功，最终分量数n−(n−1)=1，因此连通，不需最后再逐点扫描。这个证明适用于本例保留自环/平行边的输入政策。
- 按集合大小将小树挂到大树，并做路径压缩。不要直接把parent[a]=b当合并代表，那可能破坏结构；也不要把原图中的parent关系与并查集代表混淆。
- BFS替代方案是在边数正确后从任一点访问全部节点，若访问数n便为树；需要O(n+m)邻接表。若不用边数预检，只靠DFS找环，要处理父边和并行边的边编号，否则可能忽略第二条平行边。
- 调试至少覆盖单节点、链、星、断连加环、自环和重复边。独立对照以传递闭包检查全连通，并结合原始边数，避免复用并查集细节。
手动走一遍
n=4，边(0,1),(1,2),(2,3)全部合并成功，是树。边(0,1),(1,2),(2,0)虽然也是3条，却第3条发现两端同代表，且节点3孤立，返回False。n=1且空边返回True。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def valid_tree(n, edges):
if type(n) is not int or n < 1:
raise ValueError('n must be a positive integer')
if any(len(edge) != 2 or any(type(v) is not int or not 0 <= v < n for v in edge) for edge in edges):
raise ValueError('invalid edge endpoint')
if len(edges) != n - 1:
return False
parent = list(range(n))
size = [1] * n
def root(v):
while v != parent[v]:
parent[v] = parent[parent[v]]
v = parent[v]
return v
for a, b in edges:
x, y = root(a), root(b)
if x == y:
return False
if size[x] < size[y]:
x, y = y, x
parent[y] = x
size[x] += size[y]
return True
复杂度
设m为边数，输入验证O(m)，通过边数筛选后并查集O(n+m α(n))摊还时间，O(n)工作空间；当m≠n−1时无需分配parent数组。BFS版时间与空间O(n+m)。
易错点与追问
容易失分的边界
- 仅检查m=n−1就判树。
- 只从0检测环而不检查其他分量。
- 擅自去重平行边改变输入合同。
- 将有向树判定套成无向并查集。
继续深挖
- 如果要求返回造成环的第一条边？
- 如何判断有向图是否为有根树？
- 边流动态添加时怎样维护分量数？
- 支持删除边为什么普通并查集不够？
