LeetCode 261. 以图判树

约 5 分钟
文章信息 2 个分类 4 个标签
分类
LeetCode 中等
标签
深度优先搜索 广度优先搜索 图 并查集

题目描述

✅ 261. 以图判树

题意分析

给定 n 个节点和若干条无向边，判断整个图是否恰好是一棵树。树需要同时满足全部节点连通和没有环，不能只检查其中一部分。

单个节点且没有边也是树。孤立节点属于输入中的节点，即使它没有出现在任何边里，也必须纳入连通性判断。

解法：边数检查加并查集判环

核心思路

[!blue]

一棵含 n 个节点的树恰好有 n - 1 条边，因此先检查数量，不满足即可拒绝。但边数正确本身还不够，某处存在环、别处不连通时也可能碰巧有这个数量，所以还要确认这些边没有形成环。

并查集初始把每个节点视为一个独立连通块。处理无向边时，先找两端所在集合的根：根相同意味着两端之间已经存在路径，再加这条边就会成环，立即失败；根不同则安全合并两块，连通块数恰好减少一。

如果 n - 1 条边全部成功连接不同集合，从最初 n 块恰好减少到一块，同时从未形成环，因此既无环又连通，不必再额外遍历检查每个节点是否可达。这解释了为什么边数检查与逐边判环合起来已经是充分条件。

查找时将节点指向祖父，逐步压短集合树路径；合并时把较小集合根接到较大集合根下，避免并查集自身退化成长链。这些父指针只表示连通关系，不是原图里的实际道路方向。

解题步骤

  1. 边数不等于 n - 1 时返回 false。
  2. 为全部节点初始化独立的集合根和大小。
  3. 依次查找每条边两端的集合根，相同则返回 false。
  4. 根不同时，按集合大小合并，并更新新根的集合大小。
  5. 所有边都成功合并后返回 true。

代码实现

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) {
            return false;
        }

        int[] parent = new int[n];
        int[] size = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        for (int[] edge : edges) {
            int a = find(parent, edge[0]);
            int b = find(parent, edge[1]);

            if (a == b) {
                return false;
            }

            if (size[a] < size[b]) {
                int t = a;

                a = b;
                b = t;
            }

            parent[b] = a;
            size[a] += size[b];
        }

        return true;
    }

    private int find(int[] parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }

        return x;
    }
}

func validTree(n int, edges [][]int) bool {
    if len(edges) != n-1 {
        return false
    }
    parent, size := make([]int, n), make([]int, n)
    for i := range parent {
        parent[i] = i
        size[i] = 1
    }
    find := func(x int) int {
        for parent[x] != x {
            parent[x] = parent[parent[x]]
            x = parent[x]
        }
        return x
    }
    for _, edge := range edges {
        a, b := find(edge[0]), find(edge[1])
        if a == b {
            return false
        }
        if size[a] < size[b] {
            a, b = b, a
        }
        parent[b] = a
        size[a] += size[b]
    }
    return true
}

复杂度分析

  • 时间复杂度：$O(n + E\alpha(n))$，初始化为 $O(n)$，E 条边执行并查集查找与合并，路径压缩和按大小合并提供近常数均摊代价。通过边数检查时 E = n - 1。
  • 空间复杂度：$O(n)$，保存集合父指针与大小数组。

关键点总结

[!green]

  • n - 1 条边是必要条件，不能单独用来认定是树。
  • 每次不同集合的成功合并减少一个连通块，同集合边则形成环。
  • 恰好成功合并 n - 1 次，自动把所有节点连成一个集合。
  • 所有节点都初始化，包括边列表里未出现的孤立节点。

易错点总结

[!yellow]

  • 只检查边数，会漏掉某个分量成环、其他分量仍断开的情况。
  • 只确认没有环，不限制边数或检查连通，会把多个独立的树当成一棵树。
  • 合并时修改普通端点而不是集合根，可能破坏现有集合结构。
  • 忽略未出现在边里的节点，会错误缩小需要连通的范围。
  • 单节点无边直接判失败，会漏掉合法的最小树。

相似题目

题目 难度 关联与区别
684. 冗余连接 中等 同样用并查集检测一条边是否让两个已连通端点形成环，原题要返回这条边。
547. 省份数量 中等 复用集合合并与连通块计数，本题再结合边数判断是否为树。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/44317217
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！