题目描述
思路解析动画文字版
记住这一句，下面每条边都在套它。
起手：11 个节点、10 条边。先数边：10 == 11-1，边数刚好够。再逐条加边，看会不会成环、最后连不连得成一块。
看边 (0,1)：0 的根是 0，1 的根是 1，根不同 → 这条边接通了两个原本分开的块，安全合并。
合并：让根 1 指向根 0，两块并成一块（同色）。连通块数 -1 → 10。
看边 (0,2)：0 的根是 0，2 的根是 2，根不同 → 这条边接通了两个原本分开的块，安全合并。
合并：让根 2 指向根 0，两块并成一块（同色）。连通块数 -1 → 9。
看边 (0,3)：0 的根是 0，3 的根是 3，根不同 → 这条边接通了两个原本分开的块，安全合并。
合并：让根 3 指向根 0，两块并成一块（同色）。连通块数 -1 → 8。
看边 (1,4)：1 的根是 0，4 的根是 4，根不同 → 这条边接通了两个原本分开的块，安全合并。
合并：让根 4 指向根 0，两块并成一块（同色）。连通块数 -1 → 7。
看边 (1,5)：1 的根是 0，5 的根是 5，根不同 → 这条边接通了两个原本分开的块，安全合并。
合并：让根 5 指向根 0，两块并成一块（同色）。连通块数 -1 → 6。
看边 (2,6)：2 的根是 0，6 的根是 6，根不同 → 这条边接通了两个原本分开的块，安全合并。
合并：让根 6 指向根 0，两块并成一块（同色）。连通块数 -1 → 5。
看边 (2,7)：2 的根是 0，7 的根是 7，根不同 → 这条边接通了两个原本分开的块，安全合并。
合并：让根 7 指向根 0，两块并成一块（同色）。连通块数 -1 → 4。
看边 (3,8)：3 的根是 0，8 的根是 8，根不同 → 这条边接通了两个原本分开的块，安全合并。
合并：让根 8 指向根 0，两块并成一块（同色）。连通块数 -1 → 3。
看边 (4,9)：4 的根是 0，9 的根是 9，根不同 → 这条边接通了两个原本分开的块，安全合并。
合并：让根 9 指向根 0，两块并成一块（同色）。连通块数 -1 → 2。
看边 (5,10)：5 的根是 0，10 的根是 10，根不同 → 这条边接通了两个原本分开的块，安全合并。
合并：让根 10 指向根 0，两块并成一块（同色）。连通块数 -1 → 1。
所有边加完没成环，连通块数 = 1（全连成一块，同色）。边数 10 == 11-1，无环又连通 → 是一棵树（true）。
边界先想清。
两个高频追问。
参考代码
class Solution { int[] parent; public boolean validTree(int n, int[][] edges) { if (edges.length != n - 1) return false; parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; for (int[] e : edges) { int ra = find(e[0]), rb = find(e[1]); if (ra == rb) return false; parent[rb] = ra; } return true; } int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }}复杂度
- 时间：O(n + m·α)，m 条边，每次 find 近乎常数（路径压缩）
- 空间：O(n)，一个 parent 数组
易错点
面试追问把动画讲成自己的话
追问为什么边数 == n-1 加无环就一定连通？
追问不用并查集还能怎么判？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
单词接龙
LeetCode 127 · 困难 · 沿着 图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题