【图, 并查集】以图判树

题目

261. 以图判树

---

给定编号从 0 到 n - 1 的 n 个结点。给定一个整数 n 和一个 edges 列表，其中 edges[i] = [ai, bi] 表示图中节点 ai 和 bi 之间存在一条无向边。

如果这些边能够形成一个合法有效的树结构，则返回 true ，否则返回 false 。

示例 1：

输入: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
输出: true

示例 2:

输入: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
输出: false

提示：

• 1 <= n <= 2000
• 0 <= edges.length <= 5000
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• 不存在自循环或重复的边

解题

方法一：并查集

思路

判断一颗树是否合法的依据有两点：

1. 树中没有形成环 如果形成环就变成图了，而判断有没有环的方法也很简单：就是查看每条边上的两个节点对应的祖宗节点是不是同一个。
2. 连通分量的个数为 1 显然如果连通分量的个数大于1，最多也只能算森林，而不能算作一颗树。

上面这两个条件都可通过并查集实现。

代码

class Solution {
    private int[] nodeToRoot;

    public boolean validTree(int n, int[][] edges) {
        nodeToRoot = new int[n];
        for (int i = 0; i < n; i++) nodeToRoot[i] = i;
        for (int[] edge : edges) {
            if (find(edge[0]) == find(edge[1])) return false;
            union(edge[0], edge[1]);
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (i == nodeToRoot[i]) count++;
        }
        return count == 1;
    }

    private void union(int p, int q) {
        nodeToRoot[find(p)] = find(q);
    }

    private int find(int n) {
        if (n != nodeToRoot[n]) nodeToRoot[n] = find(nodeToRoot[n]);
        return nodeToRoot[n];
    }
}

优化

如果 $图的边数+1 = 图的顶点数$ 那么图中一定不会形成环，这就是一颗合法的树。

class Solution {
    private int[] unionFind;

    public boolean validTree(int n, int[][] edges) {
        if (n != edges.length + 1) return false;
        unionFind = new int[n];
        for (int i = 0; i < n; i++) unionFind[i] = i;
        for (int[] edge : edges) union(edge[0], edge[1]);
        boolean hasFoundRoot = false;
        for (int i = 0; i < n; i++) {
            if (i != unionFind[i]) continue;
            if (hasFoundRoot) return false;
            hasFoundRoot = true;
        }
        return true;
    }

    private void union(int p, int q) {
        unionFind[find(p)] = find(q);
    }

    private int find(int n) {
        while (n != unionFind[n]) {
            unionFind[n] = find(unionFind[n]);
            n = unionFind[n];
        }
        return n;
    }
}