目录
1.算法介绍
1.1什么是并查集呢，它又是用来干什么的呢？
1.2问题引入
2.算法解析
2.1初始化
2.2合并操作
2.3查找 + 路径压缩
2.4问题解决代码
3.变式突破
1.算法介绍
1.1什么是并查集呢，它又是用来干什么的呢？
逐字拆解一下，并、查、集。这个三个字，其中前面两个字都是动词，第三个字是个名词。
（1）并查集可以进行集合合并的操作（并）
（2）并查集可以查找元素在哪个集合中（查）
（3）并查集维护的是一堆集合（集）
基本原理：每个集合用一棵树来表示。树的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点
并查集算法无论是集合合并还是元素查询，时间复杂度都是接近 0（1）。
1.2问题引入
模板题：
一共有 n 个数，编号是 1∼n1，最开始每个数各自在一个集合中。
现在要进行 m个操作，操作共有两种：
M a b，将编号为 a和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；Q a b，询问编号为 a和 b的两个数是否在同一个集合中；输入格式
第一行输入整数 n和 m。
接下来 m 行，每行包含一个操作指令，指令为
M a b或Q a b中的一种。输出格式
对于每个询问指令
Q a b，都要输出一个结果，如果 a和 b在同一集合内，则输出Yes，否则输出No。每个结果占一行。
数据范围
1≤n,m≤10^5
2.算法解析
一些说明：
1.假如 n==5，就是说有5个元素1~5，分别所属在集合1到5中。
2.p数组存集合的编号，表示是哪个集合。
3.查询元素在哪个集合的函数是find(int x),会返回该元素所在的集合编号。
学习并查集模板，其实学习的就是下面三步
2.1初始化
做法：用一个数组保存对应位置元素所属集合的编号。
模板代码：
for (int i = 1; i <= n; i++) {
p[i] = i;
}很容易理解，就是将当前元素的父节点指向自己
此时p[1]==1,就表示元素1在集合1中。
用n==5举例，此时代码表示的集合的状态：
2.2合并操作
做法：若想A，B两个集合合并：可以将B集合的集合编号设置为A集合的集合编号。
模板代码：
p[find(B)]=find(A)此时代码表示的集合的状态：
2.3查找 + 路径压缩
正是因为进行了路径压缩， 并查集的时间复杂度接近 0（1）。
先看模板代码：
public static int find(int x){ //返回x所在的集合编号 + 路径压缩
//祖先节点的父节点是自己本身
if(p[x] != x){
//将x的父亲置为x父亲的祖先节点,实现路径的压缩
p[x] = find(p[x]);
}
return p[x];
}路径压缩的最终目的：让一个集合中的任意元素（用x表示）的p[x]里都存储其集合编号。
此时的集合状态:
我们从递归和回溯两方面分析：
最终 集合的状态
2.4问题解决代码
import java.util.Scanner;
public class Main {
/*一共有 n个数，编号是 1∼n，最开始每个数各自在一个集合中。现在要进行 m
个操作，操作共有两种：M a b，将编号为 a和 b
的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
Q a b，询问编号为 a和 b的两个数是否在同一个集合中；*/
/*输入格式
第一行输入整数 n和 m。
接下来 m行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。*/
static int N = 100010;
static int[] p = new int[N];
//并查集的核心操作，寻找根节点祖先 + 路径压缩
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int q = in.nextInt();
//初始化
for (int i = 1; i <= n; i++) {
p[i] = i;
}
while (q-- > 0) {
String s = in.next();
int a = in.nextInt();
int b = in.nextInt();
//合并操作
if (s.equals("M")) {
p[find(a)] = find(b);
} else if (s.equals("Q")) {
//查找
if (find(a) == find(b)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
}
public static int find(int x){ //返回x所在的集合编号 + 路径压缩
//祖先节点的父节点是自己本身
if(p[x] != x){
//将x的父亲置为x父亲的祖先节点,实现路径的压缩
p[x] = find(p[x]);
}
return p[x];
}
}3.变式突破
题目：
给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。
现在要进行 m个操作，操作共有三种：
C a b，在点 a和点 b 之间连一条边，a和 b 可能相等；Q1 a b，询问点 a和点 b 是否在同一个连通块中，a和 b 可能相等；Q2 a，询问点 a 所在连通块中点的数量；输入格式
第一行输入整数 n和 m。
接下来 m 行，每行包含一个操作指令，指令为
C a b，Q1 a b或Q2 a中的一种。输出格式
对于每个询问指令
Q1 a b，如果 a 和 b在同一个连通块中，则输出Yes，否则输出No。对于每个询问指令
Q2 a，输出一个整数表示点 a 所在连通块中点的数量每个结果占一行。
数据范围
1≤n,m≤10^5
与模板题不同处的说明：
与模板题唯一不同的是，我们要多维护数组size来记录该元素的集合中元素的个数。
1.对于数组size只保证根节点的size有意义。
2.初始化时，还要初始化每个集合内的元素数量为1。
初始化的代码：
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}3.合并a和b所在的两个集合
合并集合操作同时要记得维护集合大小关系
比如集合a合并到集合b里的代码：
p[find(a)] = find(b);
size[b] += size[a];代码：
import java.util.Scanner;
public class Main {
/* 现在要进行 m个操作，操作共有三种：
C a b，在点 a和点 b之间连一条边，a和 b可能相等；
Q1 a b，询问点 a和点 b是否在同一个连通块中，a
和 b可能相等；Q2 a，询问点 a所在连通块中点的数量；*/
/* 输入格式
第一行输入整数 n和 m。
接下来 m行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。
*/
/*输出格式
对于每个询问指令 Q1 a b，如果 a和 b在同一个连通块中，则输出 Yes，否则输出 No。
对于每个询问指令 Q2 a，输出一个整数表示点 a所在连通块中点的数量 每个结果占一行。*/
static int N = 100010;
static int[] p = new int[N];
static int[] size = new int[N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
for (int i = 1; i <= n; i++) {
p[i] = i;
size[i] = 1;
}
while (m-- > 0) {
String s = scanner.next();
if (s.equals("C")) {
int a = scanner.nextInt();
int b = scanner.nextInt();
if (find(a) != find(b)) {
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
}
} else if (s.equals("Q1")) {
int a = scanner.nextInt();
int b = scanner.nextInt();
if (find(a) == find(b)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
} else {
int a = scanner.nextInt();
System.out.println(size[find(a)]);
}
}
}
private static int find(int x) {
if (x != p[x]) {
p[x] = find(p[x]);
}
return p[x];
}
}以上为我个人的小分享，如有问题，欢迎讨论！！！
都看到这了，不如关注一下，给个免费的赞 
