力扣labuladong一刷day47天并查集

2023-12-26 16:00:33

力扣labuladong一刷day47天并查集

一、261. 以图判树

题目链接:https://leetcode.cn/problems/graph-valid-tree/
思路:本题的要求是给你一组连接边,判断是否能组成树,其实只要是无环图,就是数,那问题也就变成了是否能组成无环图。其实只要新加的这两条边对应的节点,如果原本就在同一个联通分量中,再给连上边即为环,如果这条边没加入之前两节点不属于同一联通分量,就不会成环。对于是否在同一个联通分量内这种事情是Union-Find 算法的拿手绝活。

class Solution {
    public boolean validTree(int n, int[][] edges) {
        UF uf = new UF(n);
        for (int[] edge : edges) {
            if (uf.connected(edge[0], edge[1])){
                return false;
            }
            uf.union(edge[0], edge[1]);
        }
        return uf.count == 1;
    }

    class UF {
        int[] parent;
        int count;

        public UF(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
            count = n;
        }

        int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        boolean connected(int x, int y) {
            return find(x) == find(y);
        }

        void union(int x, int y) {
            int a = find(x);
            int b = find(y);
            if (a == b) return;
            parent[a] = b;
            count--;
        }

        int count() {
            return count;
        }
    }
}

二、1135. 最低成本联通所有城市

题目链接:https://leetcode.cn/problems/connecting-cities-with-minimum-cost/
思路:本题边带权重,求的是最小生成树,构造树在上一题中已经介绍,本题只需要考虑如果最小,采用贪心的思路,可以把所有的边按照从小到大进行排序,逐个判断是否在同一联通分量,不在然后加入,最后如果联通分量为1则为最小生成树。

class Solution {
    public int minimumCost(int n, int[][] connections) {
        Arrays.sort(connections, (a, b) -> (a[2] - b[2]));
        int cost = 0;
        UF uf = new UF(n);
        for (int[] ints : connections) {
            if (!uf.connected(ints[0], ints[1])) {
                uf.union(ints[0], ints[1]);
                cost += ints[2];
            }
        }
        if (uf.getCount() != 1) return -1;
        return cost;
    }

    class UF{
        int[] parent;
        int count;
        public UF(int n) {
            parent = new int[n+1];
            for (int i = 0; i <= n; i++) {
                parent[i] = i;
            }
            count = n;
        }
        int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        boolean connected(int x, int y) {
            return find(x) == find(y);
        }
        void union(int x, int y) {
            int a = find(x);
            int b = find(y);
            if (a == b) return;
            parent[a] = b;
            count--;
        }
        int getCount() {
            return count;
        }
    }
}

三、1584. 连接所有点的最小费用

题目链接:https://leetcode.cn/problems/min-cost-to-connect-all-points/
思路:求连接所有节点的最小费用也就是求最小生成树,本题只给出了所有的点,和权重的计算方法,但是没有给边,需要我们去计算出所有的边,以及对应的权重,之后就可以使用并查集算法来进行处理,还是和上一题一样,只要需要加入的这条边的两个节点,之前不在联通,就可以加,否则加了就成环。

class Solution {
   public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                int xi = points[i][0], yi = points[i][1];
                int xj = points[j][0], yj = points[j][1];
                list.add(new int[]{i, j, Math.abs(xi - xj) + Math.abs(yi- yj)});
            }
        }
        Collections.sort(list, (a, b) -> {
            return a[2] - b[2];
        });
        UF uf = new UF(n);
        int cost = 0;
        for (int[] ints : list) {
            if (!uf.connected(ints[0], ints[1])) {
                uf.union(ints[0], ints[1]);
                cost += ints[2];
            }
        }
        return cost;
    }
    class UF{
        int[] parent;
        int count;
        public UF(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
            count = n;
        }
        int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        boolean connected(int x, int y) {
            return find(x) == find(y);
        }
        void union(int x, int y) {
            int a = find(x);
            int b = find(y);
            if (a == b) return;
            parent[a] = b;
            count--;
        }
        int getCount() {
            return count;
        }
    }
}

文章来源:https://blog.csdn.net/qq_43511039/article/details/135215256
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。