Introduction

以树来维护集合，树根节点的下标就是集合的编号。每个节点存储其父节点，用数组p[x]来存储

可以快速实现（近乎$ O(1) $）两个功能：

1. 合并两个集合
2. 判断两个元素是否在同一集合当中

Train of Thought

判断树根

对于任意一个节点x来说，其父节点的下标存储在数组p[x]中。对于根节点，我们让p[x] = x，则可以判断某点是否为树根节点

求所在集合

如果x节点不是树根，那么就跳转到他的父节点。直到找到树根

while (x != p[x]) x = p[x];

合并两个集合

令A集合的树根节点变成B集合的树根节点的爹节点，p[A] = B，可以快速合并

实际上，我们用树只是为了存储元素，而并不需要存储父子节点的关系，所以任意两个非根节点谁是爹谁是儿不重要，重要的是他们都属于一个祖宗节点就行了。

所以，我们可以实现路经压缩优化：一个x节点向上反复判断到祖宗节点时，直接令其p[x]改为祖宗节点，并且让路径上所有的爹、爷节点的p[x]都改成祖宗节点

这样，我们下次需要查找x节点，及其路径上的所有节点的所属集合时，可以直接用p[x]找到，不需要反复判断了

路经压缩：祖宗秒变爹

Code

代码实现还是有一定难度的，尤其是路经压缩优化。

我们定义一个find函数，用来查询某个节点x的祖宗节点。

我们用一个递归函数来实现，非常地妙：

int find(int x ) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

每次都会向上找一个p[x]，直到找到祖宗节点，然后给这个路径上所有用到过的节点都认祖为父