本文参考资源：
超超有爱爱-----并查集~~~chen_zan_yu的博客-CSDN博客
概述
并查集通常用作集合的合并。
并查集是一种树形结构，又叫“不相交集合”，保持了一组不相交的动态集合，每个集合通过一个代表来识别，代表即集合中的某个成员，通常选择根做这个代表。
我们先来介绍一下并查集的思想：
假设我们现在已知一些连通关系，例如(2,4),(1,2),(5,6),(3,4),(2,3)，我们用一张图来表示这个关系：
现在我们用并查集的思想把它分成几个不连通的集合：
首先我们有一个father数组，它记录的是在并查集这个树形结构中，某个节点对应的父节点是哪个，用数组表示，一开始全为0。
我们把(2,4)这个关系取出来，每次要做的操作就是把它们的根节点连接起来（一直寻找父节点直到对应的father为0），这里就把4连接到2上，然后修改father[4]的值为2.
再处理(1,2)这个关系，由于此时1和2的根节点是它本身，也是将他们连起来。把father[1]修改为2。
5和6的根节点也是它本身，将他们连起来，father[6]修改为6。
这里发现3的根节点是3，4的根节点是2，于是把2和3连接起来。把father[2]修改为3。
最后处理(2,3)的时候发现2和3的根节点都是3，于是不做处理。 最后得到的集合有两个，分别是数组中值为0的3和5。
操作
上面的图中我们为了模拟自然思想，数组的下标从1开始，而实际编程的时候数组下标从0开始，根据限制可以把没有父节点的元素的值设为-1，也可以就设为该元素的下标，也可以把下标为0的数组元素空出来，对java来说就不用一开始就把数组赋一遍值。
并查集的核心操作有两个：
find_root(x):
返回能代表x所在集合的节点，通常返回x所在集合的根节点，有递归和非递归两种方法。
union(x, y):
将包含x,y的集合合并为一个新的集合。合并两个集合的关键是找到两个集合的根节点，如果两个根节点相同则不用合并；如果不同，则需要合并。
class UnionFind {
int[] father;
//构造函数，这里把它们全部赋值为-1，代表没有父节点
public UnionFind(int totalNodes) {
father = new int[totalNodes];
Arrays.fill(father,-1);
}
//合并两个集合，即将它们的根节点连接。
void union(int node1, int node2) {
int root1 = find_root(node1);
int root2 = find_root(node2);
if (root1 != root2) {
father[root2] = root1;
}
}
// 找到一个数组元素对应的根节点
int find_root(int node) {
while (father[node] != -1)
node = father[node];
return node;
}
//检查两个数组元素代表的集合是不是相连的，如果是说明它们的根节点是相同的
boolean isConnected(int node1, int node2) {
return find_root(node1) == find_root(node2);
}
}
操作优化
并查集的优化主要包括：
+ 合并时平衡树的高度（比较要合并的两个树的高度）。
+ 查询时的优化：路径压缩
平衡树的高度这里不详细讲。
路径压缩就是每次查询的时候都会顺着路径查找，最终找到根节点。而找到了根节点之后可以将查询的节点的father直接连到根节点上，实际上也是减小树的高度。
算法题讲解
原题
蓝桥杯历届试题 合根植物
问题描述
w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
输入格式
第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。
接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)
接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。
格子的编号一行一行，从上到下，从左到右编号。
比如：5 * 4 的小格子，编号：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
样例输入
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
样例输出
5
样例说明
其合根情况参考下图
解答
这就是一道完全不加修饰，几乎要明示你这道题应该要用并查集的算法题。
按照我们之前的讲解，可以写出如下代码：
import java.util.Scanner;
public class Main {
static int[] father;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
//先算出数组的大小，这里我们从下标为1开始记录数据，就可以用0来代表没有父节点了。
father = new int[scanner.nextInt()*scanner.nextInt()+1];
int n = scanner.nextInt();
for(int i = 0;i < n;i ++){
union(scanner.nextInt(),scanner.nextInt());
}
int sum = 0;
//看看合并完之后还有多少个没有父节点的元素，就是集合的个数
for(int i = 1;i<father.length;i++){
if(father[i] == 0) sum+=1;
}
System.out.println(sum);
}
//合并两个集合，即将它们的根节点连接。
static void union(int node1, int node2) {
int root1 = find_root(node1);
int root2 = find_root(node2);
if (root1 != root2)
father[root2] = root1;
}
// 找到一个数组元素对应的根节点，这里由于整道题我们只需要查找一次就不优化了。
static int find_root(int node) {
while (father[node] != 0)
node = father[node];
return node;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/%e6%8b%89%e5%b8%ae%e7%bb%93%e6%b4%be%e7%9a%84%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84-%e5%b9%b6%e6%9f%a5%e9%9b%86/
