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

��欢迎光临

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

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

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

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

努力的苏泽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      
历届试题 国王的烦恼
问题描述
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