# 写在前面

并查集，实际上是一种数据结构，维护了一个不相交动态集的集合 $\mathbb{S} = {S_1, S_2, S_3, \dots, S_n}$ 之间的从属关系，例如：

这样一个数据结构需要满足以下操作：

MAKE-SET (x) ：建立一个新集合，唯一元素就是x
FIND-SET (x) ：返回一个指针，指向包含x的（唯一）集合的代表假设已经有指针指向x，无需再在数据结构中搜索x
UNION (x, y)：将包含x和y的两个动态集合（表示为Sx和Sy）合并成一个新的集合，即这两个集合的并集。

# Intro

我们不从太算法导论的角度来引入，换一个更加实际的情境。

问题如下：

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

对于这个问题，我们可以建立模型，把所有人划分到若干个不相交的集合中，每个集合里的人彼此是亲戚。

于是，在经过一系列认亲操作后，我们为了判断两个人是否为亲戚，只需看他们是否属于同一个集合即可。

# Easy Version

并查集的重要思想在于：用集合中的一个元素代表集合，也就是说每个集合会选出一个代表（或者说祖宗），假设上题为：

给定 $8$ 个人，编号分别为 $1, 2, \dots, 8$，其初始状态为下图所示：

init

其中，箭头表示其所属关系，在初始状态下，每个人只与自己具有亲戚关系（每个人是自己的祖宗）

随后，我们给出一系列输入 $x, y$ ，表示 $x$ 与 $y$ 之间存在亲戚关系：

例如，我们给出 $1, 3$，也就是说 $1, 3$ 是亲戚，那么我们需要把 $1$ 和 $3$ 合并起来，然后选出一个作为这个亲戚谱系的代表，这里我们选择前面一个作为代表（或者说我们每次都让 $y$ 认 $x$ 当祖宗）：

Step-1

（这里，我们让相同集合内的元素都变成同一个颜色的）

于是，3 认 1 作了祖宗，现在 1 和 3 都在一个集合中了，且集合的代表元素为 1

接着，我们给出$2, 3$ ，但我们发现 3 认了 1 作祖宗，没办法认 2 做祖宗了，但是输入告诉你这两个人是一个谱系里面的，那么我们就让 2 认 1 作祖宗：

Step-2

然后经过一番认祖归宗之后，我们得到这样的一个谱系图：

Final State

很显然可以发现，这里只有两个谱系了，一个是 1 当祖宗的谱系，另外一个是 6 当祖宗的谱系

我们可以简单写出这种方法对应的代码.

初始化 ：让自己作为自己的祖宗

const int N = 1e5 + 10;
int fa[N];

void init(int n){
    for(int i = 1; i <= n; i++){
        fa[i] = i
    }
}

查询：给定一个元素 x ，查找其所属的集合（找到它的祖宗）

inline int find(int x){
    if(fa[x] == x)
        return x;
    return find(fa[x]);
}

我们采用递归的写法来查询，显然我们是在自底向上一层一层的找，直到我找到了 x 的祖宗才返回

合并：给定两个元素 x, y ，将 y 合并到 x 所在的集合内（认 x 为父亲）

inline void merge(int x, int y){
    fa[find(y)] = find(x)
}

先找到两个集合的代表元素，然后将后者的父节点设为前者即可（这里顺序是无所谓的，因为已经在一个集合里面了，并不需要考虑其代表元素到底是谁）

# Optimal Version

上面的并查集的效率怎么样呢？我们可以考虑上面的 6<-7<-8 这个情景：

首先在 merge 阶段时，我们已经知道 fa[6] = 6, fa[7] = 6, fa[8] = 7

如果我们想知道 8 的祖宗是谁，那么我们会去调用 f = find(8)，然而这样我们并不会立刻返回，因为 fa[8] = 7 != 8 因此调用 find(7)，然而 fa[7] = 6 != 7 于是我们会接着调用 find(6)

也就是说，在这一条长度为 n 的链的情况下，我们如果查询了最后一个元素（最坏情况），我们将会递归调用 n 次 find 函数，显然这不是我们需要的算法，这样的算法在空间与时间上的效率都是极低的，怎么解决这个问题呢？

我们提出了 路径压缩 这一方法。既然我们只关心一个元素对应的 根节点，那我们希望每个元素到根节点的路径尽可能短，最好只需要一步，例如：

我们想让他变成一个菊花图。

这也很好实现，我们只需要让它在查询的过程中，边查询边让路上每个节点的父节点都变成根节点即可：

inline int find(int x){
    if (fa[x] == x)
        return x;
    else {
        fa[x] = find(fa[x]);
        return fa[x];
    }
}

沿途的父节点为 fa[x] ，到最后查询出来的根节点为 x ，这样，我们就可以让原本的长链变成一个菊花图了。

但我们有一种更优雅的方式来写上面的代码：

inline int find(int x){
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

当然，即使我们有这样的算法，实际上也无法避免在合并时会出现长链的情况，我们只是在一次慢速查询后更改了其结构，让后续的查询能够更快，并且每次我们只是压缩了一条路径，如果长链不止一条呢？

（当然路径压缩已经很快了，时间复杂度为 $\Omega(m\log_{1+\frac{m}{n}}n)$ ，但是仍然会被某些特殊的构造卡，导致 TLE ，具体的证明可以看并查集复杂度 - OI Wiki (oi-wiki.org)）

我们期望这种情况能够被避免，因此提出了 启发式合并 （或者叫按秩合并）这种优化方法，但其实大家的写法只能被称为启发式合并（

在合并时，选择哪棵树的根节点作为新树的根节点会影响未来操作的复杂度。我们可以将节点较少或深度较小的树连到另一棵，以免发生退化（退化指变为长链）

例如：

现在我们需要合并 1 和 6，那么是把 6 指向 1 对于未来的查询更友好一些还是把 1 指向 6 呢？

显然是后者，因为如果我们把 6 指向 1，会使树的深度（树中最长链的长度）加深，原来的树中每个元素到根节点的距离都变长了，之后我们寻找根节点的路径也就会相应变长。虽然我们有路径压缩，但路径压缩也是会消耗时间的，而后者是不会有这个问题的。因此，在合并的时候，我们需要采取的策略是：把简单的树往复杂的树上合并

因此，我们在这里设置一个 size[] 数组，用于记录每棵树的深度（初始时为 1，因为只有自己）：

int size[N];
void init(int n){
    for(int i = 1; i <= n; i++){
        size[i] = 1;
    }
}

这样，我们合并的代码更改如下：

inline void merge(int x, int y){
    x = find(x), y = find(y);
    if(x == y)
        return ;
    if(size[x] < size[y])swap(x, y);
    fa[y] = x;
    size[x] += size[y];
}

这样，我们就做到了启发式合并。

# Summary

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

当然，这只是最基础的并查集，还有带权并查集，并且并查集像之前所说，只是一种数据结构而已，因此会在其他种种算法中出现，例如最小生成树 MST 中 Kruskal算法，最近公共祖先 LCA 中 Tarjan 算法。

Disjoint-Set

不相交集合数据结构(disjoint-set data structure)，简称并查集（ACM培训）

# 写在前面

# Intro

# Easy Version

# Optimal Version

# Summary