Too Young Too Simple
Naive
前言
昨天（2019/6/16）作者中考结束，回到机房发现自己竟然不会写并查集
于是乎……
就有了今天的这篇博客……
何为并查集？
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。
——百度百科
嗯……
我知道你看不懂。（你要是看懂了，我就该退役了）
还是来看看通俗一点的解释吧。
江湖上有许多大侠，它们彼此之间结交朋友，同时也互相打斗。
但是，他们绝对不会打自己的朋友，同时本着“朋友的朋友就是我的朋友”的原则，他们也不会打朋友的朋友。
这样，整个江湖就能通过朋友关系而串联起来，形成一个个帮派。
就像这样：
但现在问题来了：大侠们只认识自己的朋友，那两个互不认识的人如何辨别是否属于一个帮派呐？
其实也很简单。
我们可以在每个帮派内推举出一个比较有名望的人，作为该圈子的代表人物。
这样，两人只要互相对一下自己帮派的代表是不是同一个人，就可以确定敌友关系了。
这样，每个帮派就是一个并查集
并查集的操作
查找
继续接着刚刚的故事讲起……
现在每一个帮派都有了一个代表，但不是所有人都认识代表，那么如何寻找自己的代表呐？
直接递归搜索啊
我们开一个名为pre的一维数组，用于存储每个人的上级。
比如pre[1] = 3;这就代表1的上级是3。
如果说一个人的上级是他自己，那么他就是代表了。
于是我们可以得到一个查找函数：
|
路径压缩
通过上面的结构可知，门派的组成，除了代表之外都不重要。
所以说，最后形成的门派关系结构无法预知，甚至变成一字长蛇阵也有可能。
这样的话，会大大降低查找效率。
最理想的状态就是一共只有两层结构，这样的话，每个人都可以只寻找一次就找到代表。
这样，就产生了路径压缩。
路径压缩的原理在于让每一个人都与代表交朋友，领导都直接是代表。因此，只需要把代码进行一点改动
代码如下：
int find(int root){ |
查询
要查询两个人是否在同一个帮派内，只需要判断他们的代表是不是同一个人就好了
代码如下：
if(find(a) == find(b)){ |
合并
每一次打架，都会有战胜的一方与战败的一方。
而被打败之后，他们就会找自己的上级来打架。
因此，每一个人打架实质上都是代表来打架。
而战败的一方，就会被吞并。
这样，两个帮派就合并成了一个帮派。
代码如下:int merger(int root1 , int root2){
int a = find(root1);
int b = find(root2);
pre[a] = b;
}
附件：并查集[手写模板]
描述：见洛谷P3367
源代码
|
