侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 470 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【图, 并查集】以图判树

GabrielxD
2022-05-23 / 0 评论 / 0 点赞 / 51 阅读 / 545 字 / 正在检测是否收录...

题目

261. 以图判树


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

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

示例 1:

image-20220523173029101

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

示例 2:

image-20220523173037850

输入: 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;
    }
}
0

评论区