博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
并查集
阅读量:4841 次
发布时间:2019-06-11

本文共 939 字,大约阅读时间需要 3 分钟。

  并查集,在一些有N个元素的应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。它是一种树型的数据结构,用于处理一些不相交(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。

  并查集有两种实现方式,一种是路径压缩O(1),第二种是按秩合并O(logn)。路径压缩实现与理解起来简单,且效率高,所以我们通常使用路径压缩,但是路径压缩会破坏树的结构,使它不能拆分,而按秩合并则不会。

路径压缩:

  路径压缩的思路其实很简单,就是,在我们找某个点的总父亲后把它找父亲的这条路上得所有点都直接连到总父亲身上,这样以后每次查询这个点的总父亲都是O(1),操作方法如下。

const int N=10000;int n,m,fa[N];inline getf(int u){
return fa[u]==u?u:fa[u]=getf(fa[u]);}

还有初始化for(int i=1;i<=n;++i) fa[i]=i;将每一个节点的父亲定为他自己

按秩合并:

  按秩合并是给每个点一个秩,其实就是树高每次合并的时候都用秩小的指向秩大的,可以保证树高最高为log2(n),操作的时候,一开始所有点的秩都为1 在一次合并后,假设是点x和点y,x的秩小 当然x和y都是原来x和y所在区间的顶点,设点x秩为rank[x],将fa[x]指向y,然后将rank[y]的与rank[x+1]取max,因为rank[x]为区间x的高,将它连向y之后,y的树高就会是x的树高+1,当然也可能y在另一边树高更高,所以取max

int n,m,fa[N],rank[N];int getf(int u){
return fa[u]==u?u:getf(fa[u]);}void Merge(int _u,int _v){ int u=getf(_u); int v=getf(_v); if(u==v) return; if(rank[u]

 

转载于:https://www.cnblogs.com/cold-cold/p/9991680.html

你可能感兴趣的文章
如何在本地调试微信接口
查看>>
Java二分法
查看>>
杭电acm2099
查看>>
Linux GCC常用命令
查看>>
拷贝变换3字节像素到4字节内存
查看>>
PythonDay01
查看>>
Oracle数据库的JDBC衔接
查看>>
运用 KCheckGmail 监视 Gmail
查看>>
asp.net core mvc 读取appsettings.config中文乱码问题
查看>>
asp.net 的log4net的helper类
查看>>
shell编程
查看>>
2018上IEC计算机高级语言(C)作业 第1次作业
查看>>
hdu 1753
查看>>
return ;
查看>>
td在relative模式下,IE9不显示border
查看>>
7-内置数据结构
查看>>
version control(版本控制)
查看>>
FutureTask
查看>>
JDBC的元数据
查看>>
Intel CPU参数查询网站
查看>>