题目描述
思路解析动画文字版
只看连通会漏掉环，只看无环会漏掉不连通。
树必须边数等于 n-1，且每条边 union 时不能连到同一集合。
① 判树两条件：n−1 条边 + 全连通无环：树 ＝ n 个点、恰好 n−1 条边、连成一片且无环。先查边数：4 ＝ 5−1 ✓；再用并查集逐条合并，顺手抓环。
② 合并 (0,1)：根不同 → 连接，集合 5→4：find(0)=0、find(1)=1，两端根不同 → 合并成一组。集合数 5→4。
③ 合并 (0,2)：根不同 → 连接，4→3：0 与 2 根不同 → 合并。集合数 4→3。
④ 合并 (0,3)：根不同 → 连接，3→2：0 与 3 根不同 → 合并。集合数 3→2。
⑤ 合并 (1,4)：根不同 → 连接，2→1 全连通 → true：find(1) 一路向上到根 0、find(4)=4，根不同 → 合并。集合数降到 1：5 个点连成一片、全程无环 → 是树，返回 true。
一句话记住：树必须边数等于 n-1，且每条边 union 时不能连到同一集合。
边界三连：本题真边界：单点、边不够、边够但成环。
⑥ 反例：合并时两端已同根 ＝ 环 → false：若再加一条 (1,2)：find(1)=find(2)=0，两端已在同一集合还连边 ＝ 制造了环 → 立即 false。或边数 ≠ n−1 时(多了必有环、少了必不连通)，开头就能否决。
面试追问 · 核心思路：思路：边数==n−1 卡门，再并查集逐边合并抓环。
面试追问 · 为何不必单独验连通：边数==n−1 且无环 ⇒ 自动连通，无需再验。
面试追问 · 复杂度：复杂度：并查集带路径压缩 O(n·α(n))≈O(n)。
这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=graph 连刷同类题；卡住时用 AI 答疑问“并查集为什么能 O(1) 抓环”。
参考代码
class Solution: def validTree(self, n, edges): if len(edges) != n - 1: return False parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x for a, b in edges: ra, rb = find(a), find(b) if ra == rb: return False parent[rb] = ra return True复杂度
- 时间复杂度：O(n·α(n))，路径压缩后每次 find/union 近似 O(1)，共 n−1 条边
- 空间复杂度：O(n)，parent 数组存 n 个点的归属
可套用的代码模板
记牢：边数==n−1 卡门 → 逐边 find 两端 → 同根即环返回 false → 否则合并。
Python
# 并查集判树 骨架if len(edges) != n - 1: return False # 边数先卡门parent = list(range(n))def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # 路径压缩 x = parent[x] return xfor a, b in edges: ra, rb = find(a), find(b) if ra == rb: return False # 同根 → 成环 parent[rb] = ra # 合并return True易错点
面试追问把动画讲成自己的话
追问整体思路是什么？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
单词接龙
LeetCode 127 · 困难 · 沿着 图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题