当前位置: 首页 > news >正文

“树”据结构:并查集从入门到AC

“树”据结构:并查集

    • 前言
    • 算法设计
    • 代码示例
    • 优化
    • 相关文章

前言

在一组数据中,数据被分为了不同的集合,那么其中的集合往往可以用树形来表示。而区分集合,与查找集合的元素,就会成为核心的问题。并查集主要就是解决这类问题,因此并查集算法的核心也就是查找与区分。
并查集通过一个一维数组来实现,因此,给我们提供了更大的时间和空间上的便利。通过一维数组来维护一个森林,也就是维护由不同树为子集构成的集合。
问题示例:
有10个学生,1号与2号同班,3号和5号同班,4号和6号同班,7号和3号同班,8号和10号同班,9号和2号同班,8号和4号同班。
然后一般是要求解不同的班级数or输入序号查询同班同学
这类问题都是经典的并查集模板。

算法设计

先动动笔算下我们需要的结果:
1,2,9一个班级
3,5,7一个班级
4,6,8,10一个班级
首先先将一个一维数组初始化,设数组的值为其班级序号,假设每个学生都来自不同的班级,即f[i]=i。
由此f[1]=1,f[2]=2,f[3]=3,…f[10]=10。
然后我们再把结点合并成树,树内部再做处理。
由结点合并为树:以靠左优先进行同班合并,由于输入的条目是1 2,所以2号的2班消失合并到1班
在这里插入图片描述
接下来我们要准备的函数是,搜索同班同学的归属,我们先写一个深度搜索:

int dfs(int v)
{if(a[v]==v)return v;else{dfs(a[v]);}
}

于是我们可以搜索到同班同学的最终归属。
而当我们读到输入条目:9号与2号同班的时候,由于2号班级已经消失成为了1号班级(形成了树,而不是单一结点),这时候我们将整个结点归到9号之下:
在这里插入图片描述
但这时候我们的算法没有完成,因为在最后的数组下标里,1、2、9明明同属于9班2号学生却属于1班,2向1的指针就多余了,那么我们需要略微处理下搜索算法来处优化冗余数据,也称路径压缩:
在这里插入图片描述
如此处理,当最终搜索完成的时候,只要每次存在f[i]=i,就代表了有一个独立的班级,这棵树的最终父节点为i。

代码示例

初始化数据

scanf("%d %d",&n,&m);//输入学生数与数据条目数for(i=0;i<=n;i++){f[i]=i;//初始化}for(i=1;i<=m;i++){scanf("%d %d",&x,&y);//输入每组同班条目Merge_(x,y);//合并函数}

合并函数:
进行同班合并
t1与t2代表了v和u的祖先结点,如果t1与t2不相等,t2从下至上一整支需要归并到t1下

void Merge_(int v,int u)
{int t1=0,t2=0;t1=getf(v);//查找根部归属t2=getf(u);if(t1!=t2){f[t2]=t1;}}

搜索函数只需要在上文的基础上稍稍加强一下

int getf(int v)
{if(f[v]==v)return v;else{f[v]=getf(f[v]);//路径压缩return f[v];}
}

到这里,我们拿上文的题目来做输入输出示例:
有10个学生,1号与2号同班,3号和5号同班,4号和6号同班,7号和3号同班,8号和10号同班,9号和2号同班,8号和4号同班。
求学生来自多少个不同班级
那么用变量 j 来扫描搜索结果:

for(i=1;i<=n;i++){if(f[i]==i){j++;}}

在这里插入图片描述
得解分为3个班级。

优化

并查集的优化思路不少,但核心都在于,如何高效的来合并树,也就是谁向谁合并。
通俗的说,既然合并的过程是修改被合并的树的祖先认知,由于修改的过程是把树回溯,那么显然,被合并的树越小,速度就会越快,反之越慢。
前文中我们使用的是向左边的树合并,那么现在我们可以始终保持小树向大树合并:
先去声明一个size数组,来表示树的结点数量,并全部初始化为1

void Merge_(int v,int u)
{int t1=0,t2=0;t1=getf(v);t2=getf(u);if(t1!=t2){if (size[t1] > size[t2]) {//比较大小,然后由小并大f[t2] = t1;size[t1] += size[t2];} else {f[t1] = t2;size[t2] += size[t1];}}}

相关文章

二叉树从入门到AC(1)构建和前中后序遍历
二叉树从入门到AC(2)深度与层次遍历
二叉树从入门到AC(3)完全二叉树与堆

http://www.lryc.cn/news/438178.html

相关文章:

  • 高级java每日一道面试题-2024年9月11日-数据库篇-事务回滚的常见原因有哪些?
  • 目标检测中的解耦和耦合、anchor-free和anchor-base
  • git rev-parse
  • 【Unity】在Unity 3D中使用Spine开发2D动画
  • 考试:软件工程(01)
  • 数据结构应用实例(三)——赫夫曼编码
  • 关于Spring Cloud Gateway中 Filters的理解
  • 【实践】应用访问Redis突然超时怎么处理?
  • Spring Cloud Alibaba核心组件Nacos/Seata/Sentinel
  • Ubuntu搭建FTP服务器
  • Redis在单线程下删除大Key会发生什么?怎么删除大Key?
  • 《Exploit temporal cues in multi-camera 3D object detection》论文泛读
  • 十四、centos7 yum报错:cannot find a valid baseurl for repo:base/7/x86_64的解决方案
  • qt使用对数坐标的例子,qchart用QLogValueAxis坐标不出图解决
  • Python 爬虫入门 - 爬虫 requests 请求
  • flink中startNewChain() 的详解
  • uniapp 苹果安全域适配
  • linux使用命令行编译qt.cpp
  • Ubuntu 22.04 LTS 上安装 Docker
  • 2024秋季云曦开学考
  • 基于STM32与Qt的自动平衡机器人:从控制到人机交互的的详细设计流程
  • C#使用ZipFile的方法CreateFromDirectory
  • Redis 哨兵模式的选举算法是什么?
  • Linux shell编程学习笔记80:gzip命令——让文件瘦身
  • 【字幕】恋上数据结构与算法之01为什么要学习数据结构与算法
  • 120页ppt丨集团公司战略规划内容、方法、步骤及战略规划案例研究
  • 滚雪球学SpringCloud[2.3]:服务发现与负载均衡详解
  • 商务英语口语之聚会宴饮常用口语柯桥培训到蓝天广场
  • 【C#】VS插件
  • 嵌入式C语言自我修养:C语言的面向对象编程思想