并查集是一种用来维护多个集合（或对象）之间集合关系的数据结构，在很多题目中可以直接应用。它也经常被用在图论的算法优化中，是一种简单实用，又十分重要的数据结构

题目引入

例题1

有n（1 <= n <= 20）个元素，分别属于编号为1-n的集合。现有t（1 <= t <= 20）次询问，每次询问对应如下两种操作：
A：将两个元素所在的集合合并
B：询问两个元素是否在同一集合中

解答：直接开数组模拟
对于操作A：遍历所有数组，寻找两个元素所在的集合，将一个集合中的元素全部移入另一个集合
对于操作B：依然遍历寻找集合，判断集合编号是否相同

例题2

题目要求不变，数据范围改为：1 <= n <= 10000, 1 <= t <= 200000

解答：暴力模拟肯定超时，需要并查集

定义

并查集是由若干树（又称森林）组成的。起始时所有结点无儿子，且父亲为它本身。

在合并操作后，如果两个节点属于同一棵树，那么他们属于同一个集合。换而言之，一棵树的所有节点构成一个集合
如图，将1合并到2后，1，2构成一棵树，则1，2属于同一个集合

实现

储存

我们一般使用数组来维护并查集：
定义一个fa（father）数组，记录每个结点的父节点
根据定义，每个结点的父亲需初始化为它自己，即fa[i] = i
代码如下：

//初始化部分
int fa[100005], n;
//n：集合个数

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        fa[i] = i;
}

基本操作

从字面上就能够看出，并查集的基本操作就是“并”和“查”，也就是例题中的两种操作
我们先来研究怎么“查”

查询

根据定义，我们不难得到这样的性质：

在并查集中，每个结点有且仅有一个最高祖先（即树的根），这个祖先的父亲是他自己

有了这样的性质，我们不难发现，判断两个结点是否属于同一个集合，等价于判断他们的最高祖先是否相同
那么，我们的核心任务便成了如何找到每个结点的最高祖先
我们只需要根据fa数组，寻找它的父亲，再寻找父亲的父亲，再寻找父亲的父亲的父亲……直到找到一个结点，它的父亲是它自己，那么我们就找到了最高祖先。
对于查询操作，我们常用递归写法，代码如下：

//查找部分
int find(int x) {
    if(x == fa[x])          //x == fa[x]当且仅当x为最高祖先
        return x;
    return find(fa[x]);     //递归找爸爸。。。
}

综上所述，我们判断两个结点x, y是否属于同一个集合，只需判断find(x)和find(y)是否相等即可

合并

那我们怎么将两个结点x, y所在的集合合并为一个集合呢？
我们只有一个fa数组，当然还是从它入手了
我们发现，除了根结点的fa可以用，其他的fa都不是空闲的：随意改变这些fa的值会让以它为根的子树从原集合脱离
所以我们还是要找到根，也就是最高祖先。之前的find()便派上用场了
如果我们现在找到了x的最高祖先t，那么我们只需要让fa[t] = y，以t为根的这棵树就成为了y这棵树的子树，那么根据定义，这两个集合便成为一个集合了
代码如下：

//合并操作（有漏洞）
void merge(int x, int y) {
    int t = find(x);
    fa[t] = y;
}

我们的想法是正确的，但是遗漏了一点：如果x和y本来就在一个集合中怎么办？如果按我们刚才的想法操作，那么并查集就可能会变成一个有环图，再次find的时候就会死循环
所以，我们还要先判断x, y是否属于同一个集合，如果属于，则不进行任何操作
到了这里，我们再回想之前的合并操作：我们直接将t并到了y上。其实，我们可以将t并在y的最高祖先上，不难发现这样的操作和刚才所能达到的效果是相同的。但是，之前的操作会使下次find的时间增加：合并后，如果find某个原来在x这棵树上的结点，那么它一定要先到y，再从y找到y的最高祖先。而如果直接合并到y的最高祖先，那么就可以跳过y到它的最高祖先这一段路径，时间复杂度减少O(y的深度)
代码如下：

//合并操作
void merge(int x, int y) {
    x = find(x);
    y = find(y);            //将x, y分别赋值为他们各自的最高祖先
    if(x == y)              //如果已经在一个集合，直接返回
        return;
    fa[x] = y;              //将x的最高祖先并到y的最高祖先
}

这就是并查集的基本操作，但是，如果数据喜（bian）人（tai），这样朴素的做法还是会超时。下一节将重点介绍并查集的优化策略