Too Young Too Simple

Naive

前言

昨天(2019/6/16)作者中考结束,回到机房发现自己竟然不会写并查集

于是乎……

就有了今天的这篇博客……


何为并查集?

并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。
——百度百科

嗯……

我知道你看不懂。(你要是看懂了,我就该退役了)

还是来看看通俗一点的解释吧。

江湖上有许多大侠,它们彼此之间结交朋友,同时也互相打斗。

但是,他们绝对不会打自己的朋友,同时本着“朋友的朋友就是我的朋友”的原则,他们也不会打朋友的朋友。

这样,整个江湖就能通过朋友关系而串联起来,形成一个个帮派。

就像这样:

V7LIKS.png

但现在问题来了:大侠们只认识自己的朋友,那两个互不认识的人如何辨别是否属于一个帮派呐?

其实也很简单。

我们可以在每个帮派内推举出一个比较有名望的人,作为该圈子的代表人物。

这样,两人只要互相对一下自己帮派的代表是不是同一个人,就可以确定敌友关系了。

这样,每个帮派就是一个并查集


并查集的操作

查找

继续接着刚刚的故事讲起……

现在每一个帮派都有了一个代表,但不是所有人都认识代表,那么如何寻找自己的代表呐?

直接递归搜索啊

我们开一个名为pre的一维数组,用于存储每个人的上级。

比如pre[1] = 3;这就代表1的上级是3。

如果说一个人的上级是他自己,那么他就是代表了。

于是我们可以得到一个查找函数:


int find(int root){
if(pre[root] == root){
return root;
}
else{
return find(pre[root]);
}
}


路径压缩

通过上面的结构可知,门派的组成,除了代表之外都不重要。

所以说,最后形成的门派关系结构无法预知,甚至变成一字长蛇阵也有可能。

这样的话,会大大降低查找效率。

最理想的状态就是一共只有两层结构,这样的话,每个人都可以只寻找一次就找到代表。

这样,就产生了路径压缩。

路径压缩的原理在于让每一个人都与代表交朋友,领导都直接是代表。因此,只需要把代码进行一点改动

代码如下:

int find(int root){
if(pre[root] == root){
return root;
}
else{
return pre[root] = find(pre[root]);
}
}


查询

要查询两个人是否在同一个帮派内,只需要判断他们的代表是不是同一个人就好了

代码如下:

if(find(a) == find(b)){
cout << "YES" << endl;
}
else{
cout << "NO" << endl;
}

合并

每一次打架,都会有战胜的一方与战败的一方。

而被打败之后,他们就会找自己的上级来打架。

因此,每一个人打架实质上都是代表来打架。

而战败的一方,就会被吞并。

这样,两个帮派就合并成了一个帮派。

代码如下:

int merger(int root1 , int root2){
int a = find(root1);
int b = find(root2);
pre[a] = b;
}


附件:并查集[手写模板]

描述:见洛谷P3367

源代码

#include<iostream>
#define N 100001

using namespace std;

int pre[N];

int find(int root){
if(pre[root] == root){
return root;
}
else{
return pre[root] = find(pre[root]);
}
}

int main(){
int n , m;
int x , y , z;
cin >> n >> m;
for(int i = 1; i <= m; i ++){
cin >> z >> x >> y;
if(z == 1){
pre[find(x)] = find(y);
}
if(z == 2){
if(find(x) == find(y)){
cout << "Y" << endl;
}
else{
cout << "N" << endl;
}
}
}
return 0;
}
//Written By Payphone-X

THE END