介绍

并查集：从这个名字就可以看出来，并，就是合并；查，就是查找；集，就是集合。并查集，就是高效处理集合的合并和查询。

Find操作

比如下图有三个集合，每个集合有一些元素，都从0-9的序号排好了序。每个元素都是互不相交的。我们有时需要查找某个元素属于那个集合，这在并查集中就称为查找操作，也叫Find操作。

就例如查找元素$4$所在的集合，很明显，就是$2$号集合，所以，元素$4$执行Find操作的结果就是2号集合

Union操作

我们有时也需要合并两个元素所在的集合，这在并查集中就称为合并操作，也叫Union操作。

就例如合并元素$6$和元素$3$所在的集合，就要先找到元素$6$和元素$3$所在集合的编号，再把这两个集合合二为一就可以了。

更方便地执行

那么我们怎么方便在计算机上操作和存储呢？我们可以把集合组织成树形结构，且不一定是二叉树。那么这三个树也就构成了一个森林（不知道的可以彻底学习一下树和二叉树）。

那么为什么可以组成树形结构呢？因为一棵树只有一个根节点，我们可以用根节点的编号表示集合。

如上图，第一个集合用$1$来表示，第三个集合用$6$来表示。

这样我们就能更容易地执行Find操作了，比如节点$5$，我们就可以找到它所在集合的根节点，所以Find操作实际上就是找树的根节点。

我们也能更容易地执行Union操作，比如我们想合并节点$2$和节点$9$所在的集合，只需要先通过Find操作，找到两个节点所在集合的根节点$1$和$6$，发现他们并不属于同一个集合，那就让其中一个根指向另一个根就可以了。所以Union操作就是合并相应的根节点。

在实际编程里，我们用一个数组就可以保存这些信息。比如叫他p数组，p数组就是并查集的存储结构。

C++代码讲解

初始化

首先需要定义一个$p$数组,存储每个节点的父亲。
MAXN在实际做题时可以按情况定义。
p最开始的状态是什么呢？最开始，所有的节点都是指向自己的，所以最开始，可以定义一个初始化函数，来给p数组做初始化工作。参数n就是节点的个数，for循环就是让每个元素都指向自己。

#define MAXN 10010
int p[MAXN];
void init(int n){
	for(int i=0;i<n;i++){
		p[i]=i;
	}
}

Find和Union操作

Find 1.0

目的：找参数x的根节点
效率：取决于树的高度
时间复杂度：O(n)

int Find(int x){
	if(p[x]==x) retrun x;//判断是否到达根节点
	else return Find(p[x]);//递归调用：向 上走一层
}

Find 2.0 路径压缩

优化：在查找的路径中把查找路径上的节点都直接指向根
时间复杂度：
第一次查找：$O(n)$
下一次查找：$O(1)$
压缩了查找路径（路径压缩）

int Find(int x){
	if(p[x]==x) retrun x;
	else return p[x]=Find(p[x]);//在查找的路径中把查找路径上的节点都直接指向根
}

Union 1.0

目的：把参数x所在的集合指向参数y所在的集合

void Union(int x,int y){
	int rootx=Find(x);//找x的根节点
	int roory=Find(y);//找y的根节点
	if(rootx != rooty){
		p[rootx]=rooty;//合并
	}
}

Union 2.1比较高度再合并

按高度合并
将矮树合并到高树上，合并后高度不变
如果两棵树高度一样，合并后新树高度+1
把树的高度存储到h数组里。
与路径压缩不兼容，因为有路径压缩的存在，在查找参数x和参数y所在的树的时候，路径压缩会把x和y直接指向根节点，这样树的高度就会发生变化，而h数组存储的是路径压缩之前的高度，这样就会导致h数组存储的高度不准确。

int h[MAXN];
void Union(int x,int y){
	int rootx=Find(x);//找x的根节点
	int roory=Find(y);//找y的根节点
	if(rootx != rooty){
		if(h[rootx]<h[rooty]){//x树比y树矮
			p[rootx]=rooty;//x树指向y树
		}
		else if(h[rootx]<h[rooty]){//y树比x树矮
			p[rooty]=rootx;//y树指向x树
		}
		else{//xy两树高度相等
			p[rootx]=rooty;
			h[rooty]++;
			//或者
			p[rooty]=rootx;
			h[rootx]++;
		}
	}
}

Union 2.2 比较节点数再合并

按节点数来合并，通常节点数越多树就越高，节点数越少树就越矮。
将小树合并到大树上，合并后的节点个数就是两树的结点个数之和。
把树的节点数量存储到s数组里。
与路径压缩兼容，因为路径压缩只会改变树的高度，不会改变树的节点个数。

int s[MAXN];
void Union(int x,int y){
	int rootx=Find(x);//找x的根节点
	int roory=Find(y);//找y的根节点
	if(rootx != rooty){
		if(s[rootx]<=s[rooty]){//x树比y树小
			p[rootx]=rooty;//把x树合并到y树上
			s[rooty]+=s[rootx];//更新节点个数
		}
		else if(s[rootx]<s[rooty]){
			p[rooty]=rootx;
			s[rootx]+=s[rooty];
		}
	}
}

初始化的改动

Union的按高度合并和按大小合并统称为按秩合并，这两种写法的效率都是一样的，两种写法二选一进行运用就可以了。需要注意，初始化的时候，要把h数组或s数组初始化成1，因为最开始所有节点的高度和大小都是1。

#define MAXN 10010
int p[MAXN];
void init(int n){
	for(int i=0;i<n;i++){
		p[i]=i;
		h[i]=1;//按高度合并加上这一句
		s[i]=1;//按大小合并加上这一句
	}
}

Union 3.0 省略h和s数组

回顾一下之前所展示的p数组，根节点的值就是它本身，以区别出根节点和其他子节点。比如树2，因为3是根节点，所以它的值是3。如果想要根节点同时记录树的高度和大小，就可以把它改成负值。因为节点编号是从0开始的，负值也可以和其他非根节点区分开的。这样的话，如果想存储树的高度，就可以给p[3]设置成-2，其中的2就是树的高度。如果想存储树的节点个数，就可以将p[3]设置成-2，其中的2就是树的节点个数。

缺点：代码易读性变差。

在初始化的时候，只需要把p数组的每个位置都设置成-1；同时因为判断根节点的条件改变了，所以Find函数也需要稍作修改，改成

int Find(int x){
	if(p[x]<0) retrun x;//判断根节点
	else return p[x]=Find(p[x]);
}

当然，Union函数也需要改动

Union 3.0 按高度合并

虽然逻辑没有变化，但是比较的是负数，越小的负数树越高。

void Union(int x,int y){
	int rootx=Find(x);//找x的根节点
	int roory=Find(y);//找y的根节点
	if(rootx != rooty){
		if(p[rootx]<p[rooty]){
			//负数越小树越高
			p[rooty]=rootx;
		}
		else{
			p[rootx]=rooty;
			p[rooty]--;//高度自增1
		}
	}
}

Union 3.0 按大小合并

和按高度合并同理
注意：先叠加再赋值
如果先合并了两棵树，那么p[rooty]记录的大小就会被覆盖。

void Union(int x,int y){
	int rootx=Find(x);//找x的根节点
	int roory=Find(y);//找y的根节点
	if(rootx != rooty){
		if(p[rootx]<p[rooty]){
			//负数越小树越高
			p[rootx]+=rooty;
			p[rooty]=rootx;
		}
		else{
			p[rootx]+=rooty;
			p[rootx]=rooty;
		}
	}
}

_{最后，如果有使用洛谷网站的朋友们，感兴趣的可以加一下我的团队105568
这是招募信：https://www.luogu.com.cn/article/nf22g7ao
感谢！！！
文章总是有底线的}