【算法沉淀】刷题笔记：并查集带权并查集+实战讲解

🎉🎉欢迎光临🎉🎉

🏅我是苏泽，一位对技术充满热情的探索者和分享者。🚀🚀

🌟特别推荐给大家我的最新专栏《数据结构与算法：初学者入门指南》📘📘

希望能和大家一起学习！共同进步！

这是苏泽的个人主页可以看到我其他的内容哦👇👇

努力的苏泽http://suzee.blog.csdn.net

当谈论并查集时，我们可以继续使用上述的动物园比喻来解释它的概念。

我们可以把并查集看作是一个动物园管理系统，帮助你管理动物们的归属关系。

在这个动物园中，每个动物都有一个独特的编号，代表一个独立的元素。一开始，每个动物都是独立的，没有与其他动物建立关系。

初始化（Init()函数）就像是给每个动物分配一个编号和一个独立的笼子。这样，它们就有了一个起始的归属地。
查找函数（Find()函数）就像是动物们在寻找自己所属的笼子。当你给一个动物的编号，它会告诉你它所在的笼子。这样，你可以快速找到任何动物所属的笼子。
合并集合函数（Join()函数）就像是把两个笼子合并在一起，让两个动物的集合变成一个更大的集合。当你把两个动物放在同一个笼子里，它们就成为了同一个集合，共享同一个归属地。

class UnionFind {
    private int[] parent;

    public UnionFind(int size) {
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i; // 每个动物初始时独立成为一个集合，自己是自己的根节点
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 使用路径压缩优化，将当前动物的父节点直接指向根节点
        }
        return parent[x]; // 返回动物所属的笼子（根节点）
    }

    public void join(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY; // 将两个笼子合并，让一个根节点指向另一个根节点
        }
    }
}

历届试题国王的烦恼
问题描述
C 国由 n nn 个小岛组成，为了方便小岛之间联络，C 国在小岛间建立了 m mm 座大桥，每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而，由于海水冲刷，有一些大桥面临着不能使用的危险。

如果两个小岛间的所有大桥都不能使用，则这两座小岛就不能直接到达了。然而，只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达，他们就会安然无事。但是，如果前一天两个小岛之间还有方法可以到达，后一天却不能到达了，居民们就会一起抗议。

现在 C 国的国王已经知道了每座桥能使用的天数，超过这个天数就不能使用了。现在他想知道居民们会有多少天进行抗议。

输入格式
输入的第一行包含两个整数 n , m n, mn,m，分别表示小岛的个数和桥的数量。
接下来 m mm 行，每行三个整数 a , b , t a, b, ta,b,t，分别表示该座桥连接 a aa 号和 b bb 号两个小岛，能使用t天。小岛的编号从 1 开始递增。

输出格式
输出一个整数，表示居民们会抗议的天数。

样例输入
4 4
1 2 2
1 3 2
2 3 1
3 4 3

样例输出
2
样例说明
第一天后 2 和 3 之间的桥不能使用，不影响。
第二天后 1 和 2 之间，以及1和3之间的桥不能使用，居民们会抗议。
第三天后 3 和 4 之间的桥不能使用，居民们会抗议。

数据规模和约定
对于 30% 的数据，1 ≤ n ≤ 20 ， 1 ≤ m ≤ 100 1\leq n \leq 20，1 \leq m \leq 1001≤n≤20，1≤m≤100；
对于 50% 的数据，1 ≤ n ≤ 500 ， 1 ≤ m ≤ 10000 1 \leq n \leq 500，1 \leq m \leq 100001≤n≤500，1≤m≤10000；
对于 100% 的数据，1 ≤ n ≤ 10000 ， 1 ≤ m ≤ 100000 ， 1 ≤ a , b ≤ n ， 1 ≤ t ≤ 100000 1 \leq n \leq 10000，1 \leq m \leq 100000，1\leq a, b \leq n， 1 \leq t \leq 1000001≤n≤10000，1≤m≤100000，1≤a,b≤n，1≤t≤100000。

首先，我们需要根据输入的桥的信息构建并查集。

对于每座桥，如果它的使用天数超过了指定的天数，我们将这两个小岛合并成同一个集合。如果它的使用天数没有超过指定的天数，说明这座桥可以使用，我们不需要对这两个小岛进行合并。

接下来，我们遍历所有的桥，对于每座桥，我们查找连接的两个小岛是否属于同一个集合。如果不属于同一个集合，说明这两个小岛之间没有其他路径可以到达，居民们会抗议的天数加一。

最后，输出居民们会抗议的天数即可。

import java.util.*;

class UnionFind {
    private int[] parent;

    public UnionFind(int size) {
        parent = new int[size + 1];
        for (int i = 1; i <= size; i++) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        UnionFind uf = new UnionFind(n);

        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int t = scanner.nextInt();
            if (t <= 2) {
                uf.union(a, b);
            }
        }

        int protestDays = 0;
        for (int i = 1; i <= n; i++) {
            if (uf.find(i) == i) {
                protestDays++;
            }
        }

        System.out.println(protestDays - 1);
    }
}

第二道题

问题描述
小蓝国是一个水上王国, 有 2021 个城邦, 依次编号 1 到 2021。在任意两个城邦之间, 都有一座桥直接连接。

为了庆祝小蓝国的传统节日, 小蓝国政府准备将一部分桥装饰起来。

对于编号为 a 和 b 的两个城邦, 它们之间的桥如果要装饰起来, 需要的费用如下计算:

找到 a 和 b 在十进制下所有不同的数位, 将数位上的数字求和。

例如, 编号为 2021 和 922 两个城邦之间, 千位、百位和个位都不同, 将这些数位上的数字加起来是 (2+0+1)+(0+9+2)=14 。注意 922 没有千位, 千位看成 0 。

为了节约开支, 小蓝国政府准备只装饰 2020 座桥, 并且要保证从任意一个城邦到任意另一个城邦之间可以完全只通过装饰的桥到达。

请问, 小蓝国政府至少要花多少费用才能完成装饰。

提示: 建议使用计算机编程解决问题。

答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

这道题有两个思路：

1.动态规划

思路讲解

首先，我们定义一个二维数组dp，其中dp[i][j]表示城邦i到城邦j之间需要装饰的费用。

然后，我们可以使用动态规划的思路来计算dp数组的值。对于每对城邦(i, j)，我们可以通过考虑最后一段路径(i, k, j)来计算dp[i][j]的值，其中k是城邦j的前一个城邦。

具体地，我们可以遍历城邦k的所有可能取值（从1到2021），然后计算dp[i][j]的值。我们可以将dp[i][j]初始化为dp[i][k] + dp[k][j]，然后再添加城邦k和j之间的装饰费用cost(k, j)。其中cost(k, j)可以通过将城邦k和j的编号转换为字符串，然后遍历字符串中的每个字符，将字符转换为数字并求和得到。

最后，我们需要计算小蓝国政府至少要花费的费用，即dp[1][2021]。

public class Main {
    public static int calculateCost(int x, int y) {
        String strX = String.valueOf(x);
        String strY = String.valueOf(y);
        int cost = 0;
        for (char digit : strX.toCharArray()) {
            if (strY.contains(String.valueOf(digit))) {
                cost += Character.getNumericValue(digit);
            }
        }
        return cost;
    }

    public static void main(String[] args) {
        int[][] dp = new int[2022][2022];
        for (int i = 1; i <= 2021; i++) {
            for (int j = 1; j <= 2021; j++) {
                if (i != j) {
                    dp[i][j] = calculateCost(i, j);
                }
            }
        }

        for (int k = 1; k <= 2021; k++) {
            for (int i = 1; i <= 2021; i++) {
                for (int j = 1; j <= 2021; j++) {
                    if (i != j && i != k && j != k) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                    }
                }
            }
        }

        int answer = dp[1][2021];
        System.out.println(answer);
    }
}

2.并查集

题目将城堡看作连通带权无向图，其中城堡的编号表示图的节点，城堡之间的桥梁装饰费用表示图的边权。

首先，我们定义一个并查集数据结构，用于合并城堡所属的连通分量。

然后，我们遍历所有的桥梁，计算每座桥梁的装饰费用，并将费用作为边权存储在一个二维数组dp中。

接下来，我们使用并查集的思想，将连接费用为0的城堡合并到同一个连通分量中。

最后，我们计算所有城堡到第一个城堡的装饰费用，即累加每个连通分量中的最小边权。

这样，我们就可以得到小蓝国政府至少要花费的费用。

import java.util.Arrays;

public class Main {
    public static class UnionFind {
        private int[] parent;
        private int[] rank;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            Arrays.fill(rank, 1);
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
            }
        }
    }

    public static int calculateCost(int x, int y) {
        String strX = String.valueOf(x);
        String strY = String.valueOf(y);
        int cost = 0;
        for (char digit : strX.toCharArray()) {
            if (strY.contains(String.valueOf(digit))) {
                cost += Character.getNumericValue(digit);
            }
        }
        return cost;
    }

    public static void main(String[] args) {
        int n = 2021;
        UnionFind uf = new UnionFind(n + 1);
        int[][] dp = new int[n + 1][n + 1];

        // 构建并查集
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int cost = calculateCost(i, j);
                dp[i][j] = cost;
                dp[j][i] = cost;
                if (cost == 0) {
                    uf.union(i, j);
                }
            }
        }

        // 合并连通分量
        int[] set = new int[n + 1];
        Arrays.fill(set, -1);
        for (int i = 1; i <= n; i++) {
            int root = uf.find(i);
            if (set[root] == -1) {
                set[root] = i;
            }
        }

        // 计算最小装饰费用
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            if (set[i] != -1) {
                answer += dp[1][set[i]];
            }
        }

        System.out.println(answer);
    }
}