LeetCode 261中等图
以图判树 图解题解
这道题到底在问什么
判断无向图是否是一棵树。
- 示例
- n=5, edges=[[0,1],[0,2],[0,3],[1,4]] → true
最优解：一步一步想明白
- 3只看连通会漏掉环，只看无环会漏掉不连通。
- 4树必须边数等于 n-1，且每条边 union 时不能连到同一集合。
- 5树 ＝ n 个点、恰好 n−1 条边、连成一片且无环。先查边数：4 ＝ 5−1 ✓；再用并查集逐条合并，顺手抓环。
- 6find(0)=0、find(1)=1，两端根不同 → 合并成一组。集合数 5→4。
- 70 与 2 根不同 → 合并。集合数 4→3。
- 80 与 3 根不同 → 合并。集合数 3→2。
- 9find(1) 一路向上到根 0、find(4)=4，根不同 → 合并。集合数降到 1：5 个点连成一片、全程无环 → 是树，返回 true。
- 12一句话记住：树必须边数等于 n-1，且每条边 union 时不能连到同一集合。
- 15若再加一条 (1,2)：find(1)=find(2)=0，两端已在同一集合还连边 ＝ 制造了环 → 立即 false。或边数 ≠ n−1 时(多了必有环、少了必不连通)，开头就能否决。
- 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=graph 连刷同类题；卡住时用 AI 答疑问“并查集为什么能 O(1) 抓环”。
⚠️ 容易写错的地方
✗ 错：只查连通、忘了查环（或反之）
✓ 对：边数==n−1 ＋ 合并无环，两者一起才保证树
n 个点恰好 n−1 条边时：连通 ⟺ 无环 ⟺ 树。先卡边数，再用并查集抓环。
✗ 错：合并前不比较根，直接 parent[b]=a
✓ 对：先 find 两端根，根相同即成环 → false
两端已在同一集合还连边 ＝ 制造环，树里不允许。
✗ 错：边数 ≠ n−1 还继续跑
✓ 对：len(edges) ≠ n−1 直接 false
多于 n−1 必有环、少于必不连通，开头就能否决。
完整代码（Python / C++ / Java）
Python
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 TrueC++
class Solution {
public:
bool validTree(int n, vector<vector<int>>& edges) {
if (edges.size() != n - 1) return false;
vector<int> p(n);
iota(p.begin(), p.end(), 0);
function<int(int)> find = [&](int x){ return p[x] == x ? x : p[x] = find(p[x]); };
for (auto& e : edges) {
int a = find(e[0]), b = find(e[1]);
if (a == b) return false;
p[b] = a;
}
return true;
}
};Java
class Solution {
public boolean validTree(int n, int[][] edges) {
if (edges.length != n - 1) return false;
int[] p = new int[n];
for (int i=0;i<n;i++) p[i]=i;
for (int[] e: edges) {
int a = find(p,e[0]), b = find(p,e[1]);
if (a == b) return false;
p[b] = a;
}
return true;
}
private int find(int[] p, int x) {
if (p[x] != x) p[x] = find(p, p[x]);
return p[x];
}
}套路模板 · 并查集判树骨架
# 并查集判树 骨架
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 个点的归属
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 以图判树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
整体思路是什么？+
两步：① 先判 len(edges)==n−1，否则直接 false；② 并查集逐条合并，合并前比较两端根，根相同说明成环→false。全部合并完无环，则 n−1 条边必然把所有点连成一片，是树→true。
这道题为什么用「图」，换最直接的暴力解会差在哪？+
图抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。