?🎉🎉歡迎光臨🎉🎉

🏅我是蘇澤，一位對技術充滿熱情的探索者和分享者。🚀🚀

🌟特別推薦給大家我的最新專欄《數據結構與算法：初學者入門指南》📘📘

希望能和大家一起學習！共同進步！

這是蘇澤的個人主頁可以看到我其他的內容哦👇👇

努力的蘇澤http://suzee.blog.csdn.net

當談論并查集時，我們可以繼續使用上述的動物園比喻來解釋它的概念。

我們可以把并查集看作是一個動物園管理系統，幫助你管理動物們的歸屬關系。

在這個動物園中，每個動物都有一個獨特的編號，代表一個獨立的元素。一開始，每個動物都是獨立的，沒有與其他動物建立關系。

1. 初始化（Init()函數）就像是給每個動物分配一個編號和一個獨立的籠子。這樣，它們就有了一個起始的歸屬地。

2. 查找函數（Find()函數）就像是動物們在尋找自己所屬的籠子。當你給一個動物的編號，它會告訴你它所在的籠子。這樣，你可以快速找到任何動物所屬的籠子。

3. 合并集合函數（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);}
}