并查集和路径压缩

简介: 并查集和路径压缩

并查集的功能基本上就在他名字里了。

并是指合并两个集合,查是指查找该元素属于哪个集合。

用我看过的一篇文章来描述每一个江湖门派就是一个集合,底下不管有多少帮众,他们的头的头…最终头头就是掌门人,并查集的查就是查掌门人,并就是并两个帮派。

用father[i]来表示i的父亲结点,若father[i]==i,它就是掌门人,很容易得出查的操作:

int findfather(int k){
  int x=k
  while(x!=father[x]){
    x=father[x];
   }  
   return x;
 }

下面讲并,两个帮派怎么合并,人员统计来统计去太麻烦,干脆让一个掌门人认另一个掌门人做小弟就完事了,于是有:

void unionit(int a,int b){
  int i=findfather(a),j=findfather(b);
  father[j]=i;  
 }

如果要对该门派进行路径压缩,提高查的效率,考虑到时间问题,如果每一个帮众都直接指向掌门人,一切就简单了,这就叫路径压缩:

int findfather(int k){   //路径压缩后的查
  int x=k
  while(x!=father[x]){
    x=father[x];
  }
  while(k!=x){
    int i=father[k];
    father[k]=x;
    k=i;
  } 
  return x;
 }


当然有递归实现,但是如果考虑到路径压缩为了时间效率的话,最好还是写迭代模式好一点。


该方法在数据结构中最小生成树判断是否产生环很有用

相关文章
|
Web App开发 测试技术 API
Flutter 3.16 中带来的更新
Flutter 3.16 中带来的更新
295 0
|
机器学习/深度学习 算法 计算机视觉
YOLOv8改进-论文笔记】 AKConv(可改变核卷积):任意数量的参数和任意采样形状的即插即用的卷积
AKConv是一种可改变核卷积,旨在解决传统卷积的局限,包括固定大小的卷积窗口和卷积核尺寸。AKConv提供灵活的卷积核参数和采样形状,适应不同尺度特征。其创新点包括:1)支持任意大小和形状的卷积核;2)使用新算法确定初始采样位置;3)应用动态偏移调整采样位置;4)优化模型参数和计算效率。AKConv已应用于YOLOv8,提高网络性能。相关代码可在<https://github.com/CV-ZhangXin/AKConv>找到。
|
消息中间件 存储 运维
更优性能与性价比,从自建 ELK 迁移到 SLS 开始
本文介绍了 SLS 基本能力,并和开源自建 ELK 做了对比,可以看到 SLS 相比开源 ELK 有较大优势。
56092 249
|
12月前
|
传感器 算法 机器人
基于Arduino的3D打印六足机器人
基于Arduino的3D打印六足机器人
236 0
|
12月前
|
Ubuntu Linux 应用服务中间件
Docker容器入门实战
Docker容器入门实战
|
缓存 Linux 编译器
共享库soname机制
【7月更文挑战第4天】Linux共享库的soname机制管理版本,通过libname.so.x的形式区分主版本。soname(如libname.so.x)在程序编译时被记录,运行时动态链接器依据soname找对应的.so.x文件。linkname(libname.so)用于编译时链接。更新库时,soname不变则不影响已编译程序,新soname则需新旧版本共存。`ldconfig`用于更新系统共享库缓存。
230 3
|
人工智能 缓存 网络协议
网络层之三层交换、icmp协议、arp协议
网络层之三层交换、icmp协议、arp协议
|
存储 监控 数据库
neo4j如何查看日志信息
【5月更文挑战第2天】neo4j如何查看日志信息
751 2
|
安全 Java
JAVA反射调用方法
JAVA反射调用方法