LeetCode 261中等图
以图判树 图解题解
这道题到底在问什么
有 n 个节点（0..n-1）和若干无向边 edges。判断这张图能否构成一棵树：必须所有节点连成一块，且不含任何环。
- 输入
- n=11, edges=[[0,1],[0,2],[0,3],[1,4],[1,5],[2,6],[2,7],[3,8],[4,9],[5,10]]
- 输出
- true
最优解：一步一步想明白
- 3记住这一句，下面每条边都在套它。
- 4起手：11 个节点、10 条边。先数边：10 == 11-1，边数刚好够。再逐条加边，看会不会成环、最后连不连得成一块。
- 5看边 (0,1)：0 的根是 0，1 的根是 1，根不同 → 这条边接通了两个原本分开的块，安全合并。
- 6合并：让根 1 指向根 0，两块并成一块（同色）。连通块数 -1 → 10。
- 7看边 (0,2)：0 的根是 0，2 的根是 2，根不同 → 这条边接通了两个原本分开的块，安全合并。
- 8合并：让根 2 指向根 0，两块并成一块（同色）。连通块数 -1 → 9。
- 9看边 (0,3)：0 的根是 0，3 的根是 3，根不同 → 这条边接通了两个原本分开的块，安全合并。
- 10合并：让根 3 指向根 0，两块并成一块（同色）。连通块数 -1 → 8。
- 11看边 (1,4)：1 的根是 0，4 的根是 4，根不同 → 这条边接通了两个原本分开的块，安全合并。
- 12合并：让根 4 指向根 0，两块并成一块（同色）。连通块数 -1 → 7。
- 13看边 (1,5)：1 的根是 0，5 的根是 5，根不同 → 这条边接通了两个原本分开的块，安全合并。
- 14合并：让根 5 指向根 0，两块并成一块（同色）。连通块数 -1 → 6。
- 15看边 (2,6)：2 的根是 0，6 的根是 6，根不同 → 这条边接通了两个原本分开的块，安全合并。
- 16合并：让根 6 指向根 0，两块并成一块（同色）。连通块数 -1 → 5。
- 17看边 (2,7)：2 的根是 0，7 的根是 7，根不同 → 这条边接通了两个原本分开的块，安全合并。
- 18合并：让根 7 指向根 0，两块并成一块（同色）。连通块数 -1 → 4。
- 19看边 (3,8)：3 的根是 0，8 的根是 8，根不同 → 这条边接通了两个原本分开的块，安全合并。
- 20合并：让根 8 指向根 0，两块并成一块（同色）。连通块数 -1 → 3。
- 21看边 (4,9)：4 的根是 0，9 的根是 9，根不同 → 这条边接通了两个原本分开的块，安全合并。
- 22合并：让根 9 指向根 0，两块并成一块（同色）。连通块数 -1 → 2。
- 23看边 (5,10)：5 的根是 0，10 的根是 10，根不同 → 这条边接通了两个原本分开的块，安全合并。
- 24合并：让根 10 指向根 0，两块并成一块（同色）。连通块数 -1 → 1。
- 25所有边加完没成环，连通块数 = 1（全连成一块，同色）。边数 10 == 11-1，无环又连通 → 是一棵树（true）。
⚠️ 容易写错的地方
✗ 错：忘判边数
✓ 对：先卡 edges.length == n-1
多于 n-1 必成环、少于必不连通
✗ 错：只查环不查连通
✓ 对：无环 + 边数 n-1 ⇒ 自然连通
两条件凑齐才是树
✗ 错：同根还合并
✓ 对：同根即成环、立刻返回 false
成环就不是树，无需继续
完整代码（Java / Python / C++）
Java
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;
}
}Python
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
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 TrueC++
class Solution {
public:
vector<int> parent;
int find(int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
bool validTree(int n, vector<vector<int>>& edges) {
if ((int)edges.size() != n - 1) return false;
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
for (auto& e : edges) {
int ra = find(e[0]), rb = find(e[1]);
if (ra == rb) return false;
parent[rb] = ra;
}
return true;
}
};复杂度
时间
O(n + m·α)
m 条边，每次 find 近乎常数（路径压缩）
空间
O(n)
一个 parent 数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 以图判树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么边数 == n-1 加无环就一定连通？+
n 个点的无环图（森林）若有 k 个连通块，则恰有 n-k 条边；无环且边数 = n-1 ⇒ k=1 ⇒ 整图连通，正好是一棵树。
不用并查集还能怎么判？+
DFS/BFS 从 0 出发：遍历时遇到已访问且非父节点 ⇒ 有环；遍历结束访问数 == n ⇒ 连通。并查集胜在边流式增量、find 近乎 O(1)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 以图判树 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。