并查集可以快速的支持以下操作

1. 将两个集合合并
2. 询问两个元素是否在一个集合中

并查集可以再近乎$O(1)$的时间复杂度中完成上述操作。

思想：

可以用树的形式来存一个集合，每个集合的编号是跟节点的编号，对于每一个点，都存一下他的父节点$P_i$，这样要求他属于哪一个集合的时候，就可以找他的父亲，一直往上找，就找到根节点了，就知道是属于哪个集合了。

这样还有两个问题

问题一：如何判断树根

我们最初可以让$P_x = x$，只有有父节点之后$P_x$才会变，但根节点是没有父节点的，所以只要$P_x == x$，$x$就是根节点。

if (p[x] == x) 是根节点;
else 不是根节点;

问题二：如何求$x$的集合编号

按照最初的思想求就行。

while (p[x] != x) x = p[x];
x现在就是编号;

问题三：如何合并两个集合

直接让一个集合的根节点认另一个做爸爸

p[x] = y;

好，结束。但还有一种优化的方法。
就这问题二来说，遍历的次数跟树的高度是成正比的，我们可以进行优化。
假如一个点经历千辛万苦终于找到了根节点，我们可以让那个点经过的所有点的父亲直接变成根节点，这样就能节省很多时间，因为不管这些点走到根节点要走多少步，现在都可以一步到位，这种优化方法叫做路径压缩。

其实并查集还有另外一种优化叫做按秩合并，不过他不如路径压缩，所以就不说了。

这就是最基本的并查集，其他的得自己摸索。

模版

虽然说的很多但代码还是很少的，主要是找祖先那一段。

int find(int x){ // 返回x所在集合的编号（祖宗节点）+ 路径压缩。
    if (p[x] != x) p[x] = find(x);
    return p[x];
}

然后就没有了，其他的都得自己随机应变了。