并查集

发布时间:2018-11-10 07:41:45 作者:ex_jason 阅读量:195

并查集

并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。


简单来说的话。。

我们就是把所有能相互到达的点分装到几个集合内,以此来判断。

怎么实现?

我们可以理解为把每一个点都指向他所能到达的节点的父亲的父亲的父亲的……根节点

(设定前一个节点为后一个节点的父亲)

还有就是路径压缩

所有的点直接指向根节点


下面有一个非常生动的例子 from huangzirui


关于并查集和路径压缩:

有a,b,c三个人

假设a和b打架了,a做了b的小弟。则令f[a]=b;

后来a打赢了c 黑社会

那么c就是a的小弟了。所以,令f[c]=a;

但是,c不知道b,这不符合要求。

所以,我们必须让c的大哥变成最大的老大。

(在其中,一个人不能有两个老大。当已经有老大的人臣服时,老大也将成为胜利的人的小弟)

定义函数find

int find(int k){

                     if(f[k]==k)return k; 

                     return find(f[k]);

}

f[c]=find(a);

这时,我们可以使途中经过的人的大哥也变成老大。

//路径压缩

int find(int k){ 

                    if(f[k]==k)return k;

                    return f[k]=find(f[k]);

}

f[c]=find(a);

简直是太巧妙了!

而判定两个人的老大是否相等,只需用

if(find(a)==find(b))

就好了。


那么并查集有什么用呢

例题

引题——亲戚(relation)

【问题描述】若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。

规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。(人数≤5000,亲戚关系≤5000,询问亲戚关系次数≤5000)。


做这道题,显然并查集是比较有效的

并查集模板代码

上一篇:快速排序

我要评论 登录后才能发布评论

推荐阅读

 2018-11-17 14:31:12   ex_jason

最小生成树

 2018-11-10 20:40:14   ex_jason

LOL S8 决赛视频

 2018-11-10 07:41:45   ex_jason

并查集

 2018-11-10 07:28:04   ex_jason

写代码的小女孩

 2018-11-09 20:18:38   ex_jason

谈谈关于初赛的那些事

 2018-11-09 20:03:06   ex_jason

dijkstra 详解

  文章归档

ex_jason的博客"    我要留言
Catfish(鲶鱼) CMS V 4.8.39