261. 以图判树（中等）

Blind 75 › 261. 以图判树（中等） （第 5 章）
文章工具

题目

有 n 个节点，编号从 0 到 n-1；再给一组无向边 edges，每条边连接两个不同节点。判断这些边是否恰好构成一棵树。

一棵树必须同时满足两个条件：连通（任意两节点都可达）且无环（任意两节点之间的简单路径唯一）。

自造示例：

  • n = 6, edges = [[0,1],[0,2],[1,3],[1,4],[2,5]] → true。整张图连通，5 条边正好把 6 个节点连成一棵树。
  • n = 4, edges = [[0,1],[1,2],[2,0]] → false。节点 0、1、2 成环，节点 3 孤立：既不无环，也不连通。
  • n = 4, edges = [[0,1],[2,3]] → false。没有环，但两个连通块彼此不连通。

约束：1 ≤ n ≤ 2000；0 ≤ edges.length ≤ 5000；每条边为 [a,b]，满足 0 ≤ a,b ≤ n−1 且 a ≠ b。

思路

一句话：树 = 连通 + 无环，用一次带 parent 的 DFS/BFS 同时检查这两个条件。

最直白的做法：从每个未访问节点出发跑一遍遍历，统计连通块；再单独跑一遍环检测。这个思路正确，但要维护两套逻辑，还可能把“沿父节点原路返回”误判成环。

关键观察一：无向图 DFS 中，如果遇到一个已访问且不是父节点的邻居，说明从当前点绕了一圈回来，必定有环。因此只要在 DFS 中带上 parent，一次遍历就能判环。

关键观察二：从 0 号点出发的一次 DFS，会把与 0 相连的整块都标记为已访问。最后若还有节点没被访问，就说明图不连通。

再加一个廉价剪枝：n 个节点的树必然只有 n−1 条边。边数不是 n−1，直接 false；边数是 n−1 时，再用一次遍历验证“无环 + 全连通”。

解法

整体步骤：建邻接表 → 检查边数 → 带 parent 的 DFS 判环 → 检查是否所有节点都被访问。

输入边数检查DFS 发现是否全访问结果
6 节点树形示例5 == 6−1无环是true
三角 + 孤立点3 == 4−10-1-2 成环否false
两个连通块2 != 4−1不进入 DFS—false

第三个例子说明：边数检查能提前拦下一部分错误答案，但它只是必要条件，不能替代遍历。

下图把上面 4 个步骤串成流程，并逐步演示：

261. 以图判树（中等） 解法步骤流程图
图① 解法步骤流程图（共 4 步）。
261. 以图判树（中等） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Solution {
public:
 bool validTree(int n, vector<vector<int>>& edges) {
 if (n == 0) return true;
 if ((int)edges.size() != n - 1) return false;  vector<vector<int>> adj(n);
 for (auto& e : edges) {
 adj[e[0]].push_bac
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。