一、概念
1.定义：并查集 （英文：Disjoint-set data structure，直译为不交集 数据结构 ）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题
2.功能：并查集主要有两个功能。
- 将两个元素添加到一个集合中。
- 判断两个元素在不在同一个集合。
3.作用：并查集经常用来解决连通性问题。就是给你几组数据，他们之间存在一定关系，根据这种关系能否从一个元素到达另外一个元素。
4.主要构成：并查集主要由一个整型数组f[ ]和两个函数find( )、join( )构成。
数组 f[ ] 记录了每个点的父亲 (father) 节点是谁，函数 find(x) 用于查找指定节点 x 属于哪个集合，函数 merge(x,y) 用于合并两个节点 x 和 y 。
作用：
二、原理
当题目给你许多组数据的时候，问你谁和谁是同类。这时候我们便需要分类讨论，将同类分到一个集合中，但是这样的集合可能不止一个，也许有很多集合，所以我们需要将他们分为许多个数组存储。但是这样下来，当我们再回头去查找一个元素是哪个集合元素的同类或者添加一个新元素在它的同类集合中的时候，我们是不是需要每次都遍历一遍新建的全部数组（当然也有可能运气好一次就找到，但是我估计没人能次次碰对），这样大大增加了时间的效率，所以我们就想出来一个方法叫并查集，这样可以提高代码的时间复杂度。从这我们引出一维数组f[ ]。
比如说：我们有三个元素5，2，1它们的关系为：5->2，2->1那么我们只需要用一个一维数组来表示，即：f[5] = 2，f[2] = 1 这样就表述 5与 2 与 1连通了（有向连通图）。如果还有其他元素不在这个集合中，也可以直接添加进去：eg：f[6]=7；这些元素都可以添加进去到时候使用它们的父亲节点来查询他们是否为连通的（即是否为同类元素）。
三、merge()函数的定义和实现
1.定义：如果两个元素是连通的，则合并两个元素到一个集合中。
2.实现
void merge(int x, int y)
{
int fx = find(x);//查找x元素的根节点
int fy = find(y);//查找y元素的根节点
//如果发现两个元素根节点不同，直接让x的根节点指向y的根节点，这样两个元素就可以连通了。
if (fx != fy)
f[fx] = fy;
}四、find()函数定义和实现
1.定义：举个例子：
给出5元素，就可以通过 f[5] = 2，f[2] = 1，找到根为 1。
给出2元素，就可以通过 f[2] = 1，找到根也为1，说明 5 和 2 是在同一个集合里。这样我们就能知道这个find函数就是用来寻找两个元素的根的一个函数。其实就是通过数组下标找到数组元素，一层一层寻根过程，代码如下：
//非递归方法
int find(int x)
{
while(f[x] != x)
x = f[x];
return x;
}
递归方法
int find(int x) {
if (x == f[x]) return x; // 如果根就是自己，直接返回
else return find(f[x]); // 如果根不是自己，就根据数组下标一层一层向下找
}
五、路径压缩算法
我们这个并查集是一个树形结构，所以时间就消耗在遍历树的元素上，遍历树的元素时间大小跟树的高度有关，如果树的高度很大，那么查找路径就很长，当查找量很大的时候就容易TLE。
解决方案：找到根节点，修改查找路径上的所有节点，将他们都指向根节点。如图所示：
2.代码实现
int find(int x) {
if (x == f[x]) return x;
else return f[x] = find(f[x]); // 路径压缩
}六、模板
并查集对应着三种操作，初始化，查找和合并，这三种函数的模板总结如下所示
vector<int> f(1001);
//初始化f[]数组
//这个初始化函数可以直接写在主函数中（我一般直接写的）
void init()
{
for (int i = 0; i < n; i++)
{
f[i] = i;
}
}
//查找
int find(int x) {
if (x == f[x]) return x;
else return f[x] = find(f[x]); // 路径压缩
}
//合并
void merge(int x, int y)
{
int fx = find(x);
int fy = find(y);
if (fx != fy)
f[fx] = fy;
}七、总结
本章就讲解了并查集的原理和做法，有不足的地方欢迎指正谢谢。最后我也推荐两道题赶紧去做做吧，稍后我会发布解题方法放在我的并查集专栏中，欢迎观赏！
八、练习题