首先，我们可以听一个故事。
有许多的村庄，其实都是由一个人发展出来的，有些时候，我们想要知道两个人是不是一个村庄的，只要知道他的爸爸是哪个村庄的，这就是查找。
有一天，一个村庄的长老对另一个村庄的长老说：“欸，你们这个村庄就和我们一起吧！”但是我们知道，如果一个村子有两位长老肯定是会出问题的，所以我们可以试着让一个长老的所有人成为另一个长老的儿子，这样就可以让一个村庄合并到另一个里面了，这就是合并。
但可惜的是，如果村庄中某个人想脱离关系，这样做会让关于他的所有人都脱离关系，所以长老不允许这样做。
现在试想，如果使用二维数组（或者MAP）做这个事你会发现：

如果你尝试合并两个大村庄时，要改变长老的人太多，改不过来了！

我们试着修改一下合并的方法，发现其实直接把一个村庄的长老改了就好，因为其他人都是属于长老的，长老怎么变其他人就怎么变（而具体找长老的办法可以下翻）。

可这时，很容易发现，如果一个村庄的人只有1个，但是另一个有很多很多人。要是把人多的那个村庄合并到小村庄太划不来了，所以我们决定把小村庄合并到大村庄

而这样的代价是我们需要一个数组来存储自己的人数或者深度，但是在很多时候可以为我们优化掉很高的时间复杂度。

接着再来看看查找，我们的第一个办法是在每一个人出生的时候就记住长老是哪个。

可是我们发现，如果出现了二代（即父亲不一定是长老），再用我们的方法就不好了，因为每次有孩子出现都要去找长老问他是谁。

所以我们可以直接把数组换成存储父亲，这样每次有孩子出现只需要存父亲，这样子依然可以找到祖先（若假如孩子是第 \(N\) 代，递归时间复杂度为 \(O(n)\) ）。

但是这样做我们又会发现，害，我爸爸要知道谁是长老要弄一次，我要知道谁是长老还要再弄一次，这不白忙活吗，我只要让我爸爸永远记住自己家长老是谁，后来我直接让父亲告诉我不行吗？

这个办法好，因为我们发现我家长老是谁跟我父亲是谁没有任何关系啊，所以我们可以一次使用终生受益，（若假设上一辈为 \(N\) 代）时间复杂度在第一次查找时有 \(O(n)\) ，但是对于 \(1,2\cdots ,N-1\) 代来说找祖先只有 \(O(1)\) 的复杂度（直接读取不就行了吗）。

所以我们设计了一种数据结构叫做并查集，而我们最优的那种查找办法叫做路径压缩，最优的合并方法则叫按秩合并（但需要注意的是，所有人父亲一开是必须是自己）。R.E.Tarjan在1984年的论文中证明了所有情况下并查集的最坏时间情况：

很容易发现在仅使用路径压缩的情况下时间复杂度有\(O(m \ log \ n)\)以及其他情况下的时间复杂度。

现在我们来尝试一下实现这个事情。

按照我们的合并方式，可以假设用了一个数组 \(d\) 存储深度或者点数（儿子的个数），用数组 \(f\) 表示自己的父亲，这样很容易得到一种C++实现法：

void union(int x,int y){
	if(d[x]<=d[y]){
		f[find(x)]=find(y);//y比x人多或者一样多，就需要把x归属到y那里。
	}
	else if(d[x]>d[y]){
		f[find(y)]=find(x);//x比y人多，就需要把y归属到x那里。
	}
}

这里的 \(find\) 函数则需要使用到我们的路径压缩。

int find(x){
	if(x!=f[x]){//初始化的时候，长老的爸爸必须是自己。
		x=find(f[x]);//通过递归找长老，在返回值的时候可以直接路径压缩。
	}
	return f[x];
}

这样我们就拥有了一个完整的并查集数据结构了。

拓展研究

关于怎么样在并查集删点这回事。（这部分纯属蒟蒻瞎想，欢迎diss）

首先最基本的问题就是我们不能够使用路径压缩了。因为路径压缩旨在不管中间的人怎么样，我和长老好就对了。但是目前的问题在于不一定我和长老中间的人没事，所以蒟蒻个人认为不能够使用路径压缩法，只能每个人都暴力递归找长老了。

我们不能够很简单地删除点，但是本蒟蒻认为，可以通过bool数组记录解决问题，如果是其他类型的还可以用MAP记录是否被删除。

记录后，如果在找点时路遇删除点，本蒟蒻认为可以回传特殊值，而这个特殊值可以表示断路的意思，这样在返回时仍然可以做小小的优化。如这个点的值是表示断路的，可以直接认为这是个断路，不必再向长老找。

推荐习题

你谷P3367
你谷P1551
你谷P3367

完