# 并查集

并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的**合并**及**查询**问题。  
它支持两种操作：

- 查找 （Find）：确定某个元素处于哪个子集；

- 合并（Union）：将两个子集合并成一个集合。

## 初始化

```cpp
void makeSet(int size)
{
    for(int i = 0;i < size;i ++)
    {
        fa[i] = i;//i就在它本身的集合里
    }
    return;
}
```

## 查找

!!! 举个例子  
几个家族进行宴会，但是家族普遍长寿，所以人数众多。由于长时间的分离以及年龄的增长，这些人逐渐忘掉了自己的亲人，只记得自己的爸爸是谁了，而最长者（称为「祖先」）的父亲已经去世，他只知道自己是祖先。为了确定自己是哪个家族，他们想出了一个办法，只要问自己的爸爸是不是祖先，一层一层的向上问，直到问到祖先。如果要判断两人是否在同一家族，只要看两人的祖先是不是同一人就可以了。  

在这样的思想下，并查集的查找算法诞生了。我们可以用代码模拟这个过程。

```cpp
int fa[MAXN]; //记录某个人的爸爸是谁，特别规定，祖先的爸爸是他自己
int find(int x) //寻找x的祖先
{
    if(fa[x] == x) //如果x是祖先则返回
        return x;
    else return find(fa[x]); //如果不是则x的爸爸问x的爷爷
}
```

显然这样最终会返回 $x$ 的祖先。

### 路径压缩

这样的确可以达成目的，但是显然效率实在太低。为什么呢？因为我们使用了太多没用的信息，我关心的是我祖先是谁，我爸爸是谁没什么关系，这样一层一层找太浪费时间，不如我直接当祖先的儿子，问一次就可以出结果了。甚至祖先是谁都无所谓，只要这个人可以代表我们家族就能得到想要的效果。**把在路径上的每个节点都直接连接到根上**，这就是路径压缩。 
于是用代码实现它。

```cpp
int find(int x)
{
    if(x != fa[x])//x不是自身的父亲，即x不是该集合的代表
    fa[x] = find(fa[x]);//查找x的祖先直到找到代表,于是顺手路径压缩
    return fa[x];
}
```

## 合并

宴会上，一个家族的祖先突然对另一个家族说: 我们两个家族交情这么好，不如合成一家好了。另一个家族也欣然接受了。  
我们之前说过，并不在意祖先究竟是谁，所以只要其中一个祖先变成另一个祖先的儿子就可以了。

```cpp
void unionSet(int x,int y)//x与y所在家族合并
{
    x = find(x);
    y = find(y);
    if(x == y)//原本就在一个家族里就不管了
    return;
    fa[x] = y;//把x的祖先变成y的祖先的儿子
}
```

### 启发式合并（按秩合并）

一个祖先突然抖了个机灵：「你们家族人比较少，搬家到我们家族里比较方便，我们要是搬过去的话太费事了。」  

启发式合并是将深度小的集合合并到深度大的集合（也称为**按秩合并**），但是笔者认为路径压缩之后它就失去意义了，或者不如按照节点数量合并，这样还可以减少下次路径压缩的工作量。（反正启发式合并用得很少，路径压缩已经够快了。）

```cpp
int size[N];//记录子树的大小
void unionSet(int x,int y)
{
    int xx = find(x),yy = find(y);
    if(xx == yy)
        return;
    if(size[xx] > size[yy])//保证小的合到大的里
        swap(xx,yy);
    fa[xx] = yy;
    size[yy] += size[xx];
}
```

## 时间复杂度及空间复杂度

### 时间复杂度

同时使用路径压缩和启发式合并之后，并查集的每个操作平均时间仅为 $O(\alpha(n))$ ，其中 $\alpha$ 为 [阿克曼函数](https://en.wikipedia.org/wiki/Ackermann_function) 的反函数，其增长极其缓慢，也就是说其平均运行时间可以认为是一个很小的常数。 

### 空间复杂度

显然为 $O(n)$。

## 经典题目

[\[NOI2015\] 程序自动分析](https://www.lydsy.com/JudgeOnline/problem.php?id=4195)

[\[JSOI2008\] 星球大战](https://www.lydsy.com/JudgeOnline/problem.php?id=1015)

[\[NOI2001\] 食物链](https://www.luogu.org/problemnew/show/P2024)

[\[NOI2002\] 银河英雄传说](https://www.luogu.org/problemnew/show/P1196)

## 其他应用

[最小生成树](/graph/mst) Kruskal 是基于并查集的算法。