【No.12】蓝桥杯可撤销并查集|查找|合并|撤销(C++)

前置知识
蓝桥杯并查集|路径压缩|合并优化|按秩合并|合根植物(C++)-CSDN博客

可撤销并查集

关键注意

  1. 可撤销并查集的撤销功能如何实现
  2. 可撤销并查集能不能用路径压缩
    可撤销并查集(Reversible Union-Find)是一种扩展了标准并查集(Union-Find)数据结构的数据结构,它允许在进行连接(union)和查询(Find)操作的同时,能够回退(Undo)或者撤销之前的操作。这种数据结构通常用于支持一些需要回滚操作的应用,比如在离线算法中或者需要进行回退的决策问题中。当然主要是应用于在线算法,因为离线算法反悔可以完全输入后在一起处理。
举例

在蓝桥王国中有n个城市,王国经常会发生地震,会导致道路塌方,好在王国科技水平比较高也就只有刚修建好的道路会塌方,王国的人们出行前会询问两个地点是否连通。所以,你需要维护一棵动态森林,初始时包含n个散点,每个点代表一个独立的集合。然后,有m个操作,支持以下三种操作:连接操作(类型1):执行操作“1 u v”,将点u和点v连接起来,形成一个道路。这表示两个点之间有一条路。
查询操作(类型2):执行操作“2 u v”,用来査询点u和点v之间是否连通。如果它们在联通,输出"Yes",否则输出“NO"
撤销操作(类型3):执行操作"3",用于撤销上一个操作。这个操作需要保证存在被撤销的操作,即必须有之前的连接操作被撤销。

分析

我们采用并查集来表示联通,类似于最小生成树Kruskal算法,这样我们很容易就能完成op1和op2这两个操作。
但是第三个操作,如何去处理呢,怎么撤回呢,我们先不考虑路径压缩和启发式合并的情况下。并查集的合并为:
Fa[Find(i)]=j,我们只需要用变量记录t=Find(i)m=Fa[Find(i)]即可。当反悔的时候我们直接Fa[t]=m即可。
图片描述
但是既没有做路径压缩,又没有做启发式合并,那么查询效率是非常低的,所以我们很难通过一些复杂的题目。
所以我们还是需要去再去考虑优化办法。

路径压缩

我们考虑可不可以使用路径压缩来优化并查集。核心在于能够解决撤销上一步的能力。
我们考虑如果使用路径压缩优化后还能够撤销吗?
我们考虑这样一个图:
这样进行撤销的时候我们很容易记得上次操作的是什么,Fa[Find(i)]=j,我们只需要用变量记录t=Find(i)m=Fa[Find(i)]即可。当反悔的时候我们直接Fa[t]=m即可。按照我们刚才考虑的就行,那如果是路径压缩之后对于路径压缩之后的右图还能否恢复呢?
图片描述
对于某一个集合一次路径压缩之后就变成了右图所示,不能找到是那两个集合合并了。
即使我们假设上次合并的是90和1,t=fa[90]=4 m=fa[4]=4,然后进行恢复,fa[4]=4然而并不能恢复,即使在恢复90,fa[90]=4之后,只是90和4被从树中摘除,然而我们看原图。
路径压缩是不行的

启发式合并

90和4之间还有个8我们还要记录8,如果中间还有很多元素,在每次查询和合并时都被压缩,我们就更难处理了,实际上经过路径压缩后的局面比我们想象的更加复杂。
所以我们不能使用路径压缩,那我们可以进行合并吗?我们知道普通合并是可以使用的,那么启发式合并或者按秩合并可以吗?
当然可以,这两种合并方式对于并查集来说是没有用影响的,无非就是a树挂在b节点上或者b树挂在节点a上面,对于并查集整体的恢复操作不会产生什么影响。

算法原理

并查集是一种树形的数据结构,它主要用于处理一些不相交集合的合并及查询问题。可撤销并查集的基本原理与并查集相似,但增加了一个撤销操作,我们需要做的就是对这一操作进行维护。
为了提高效率,我们采用启发式合并的优化方法。在可撤销并查集中,我们不使用路径压缩因为这样会破坏树形结构,导致在撤销操作时无法准确找到原始的父节点。在合并操作中,由于不使用路径压缩,查询的复杂度为 O ( d ) O(d) O(d),其中d为树的深度。为了降低树的深度,我们采用了启发式合并(或按秩合并)的方法。

那么我们可以给可撤销并查集的算法原理:

  1. 查找
    由于支持撤销操作,那么肯定不能路径压缩,否则会破坏树形结构,反悔时无法找到原本的父节点。
  2. 合并
    既然不能路径压缩,那么查询的复杂度就是0(a)的(d为深度),所以我们要尽可能地减少树的深度,于是用到了一种合并方法–启发式合并(或按秩合并)启发式合并:
    维护每个集合的大小,合并时将小的集合合并到大的集合。
    时间复杂度:合并0(1),查找0(logn)。
  3. 撤销
    用栈来记录每次合并的操作,然后进行对fa,size等变量的维护即可
代码实现
1.定义所需变量
int n, q;
int fa[20000005], sz[2000005];

struct UndoObject
{
	int pos, val;
	UndoObject(int p, int v)
	{
		pos = p;
		val = v;
	}
};

stack<UndoObject> undo_sz, undo_fa;

用一个stack,先入后出,每次的操作往里放,先进去的会被晚撤销,撤销的一定是最近的这一步
undo_sz,记录树高
undo_fa,记录它的父亲是谁

声明了一些全局变量和数据结构,用于维护并查集的状态和实现撤销操作:
·n,q;:定义了两个全局变量n和q,分别表示数量和操作次数。fa[20000005],siz[20000005];:定义了两个数组,fa 用于表示所属的集合的父节点,sz 用于表示每个集合的大小。
Undo0bject:定义了一个结构体(类) Undo0bject,用于存储撤销操作的详细信息。每个Undo0bject对象包含两个成员变量pos和val,分别表示位置和值。
undo_sz,undo fa;:定义了两个Undo0bject堆栈,undo sz 用于记录每次连接操作的集合大小和父节点信息,undo fa用于记录每次连接操作的父节点信息。
这些全局变量和数据结构主要用于在并查集的基础上实现了撤销操作。通过堆栈undo_sz和undo fa 记录每次连接操作的详细信息,程序可以在需要时撤销最近的操作,恢复到之前的状态。

2.初始化
void init(int n)
{
	for (int i = 1; i <= n; i ++)
		fa[i] = i, sz[i] = 1;  //一棵点,就是自己
	while (!undo_sz.empty())
		undo_sz.pop();  //清除之前的栈的内容
	while (!undo_fa.empty())
		undo_fa.pop();  //清除之前的栈的内容
}

static void init (int n)
{
	fa = new int[n + 1];  //要避过0
	sz = new int[n + 1];
	for (int i = 1; i <= n; i ++)
	{
		fa[i] = i;
		sz[i] = 1;
	}
	undo_sz = new Stack<>();
	undo_fa = new Stack<>();
}

初始化函数 init,用于在开始一个新的测试用例时,清空之前的状态信息,确保并査集处于初始状态。
该函数执行了以下操作:

  • 初始化 fa 和 siz 数组:使用循环将每个初始化为独立的集合,即每个的父节点是自己,每个集合的大小为 1。
  • 清空 undosz和 undo fa 栈:使用 while 循环,对两个堆栈undo sz 和 undo fa 分别调用 pop 操作,将之前的栈内容清空。
    当开始一个新的测试用例时,调用 init函数可以确保之前的状态信息不会对当前测试用例产生干扰。
    这对于在一个程序中多次执行并查集操作,每次都需要一个干净的状态时是非常有用的。
3.查询代码
int find (int x)
{
	if (x == fa[x])
		return x;
	return find(fa[x]);
}

并查集中的查找函数。并查集是一种数据结构,它能够高效地进行合并和查找操作。这个查找函数的作用是找到给定元素所在的集合的根节点。
int find(int x):定义一个函数find,它接受一个整数参数x,表示要查找的元素
if(x==fa[x])return x;: 如果x的父节点就是自己,说明x就是它所在的集合的根节点,直接返回x。
return find(fa[x]);:否则,递归地査找x的父节点的根节点,即调用find函数。将fa[x]作为参数传递给find函数,因为fa[x]是x的父节点,它所在的集合的根节点就是x所在的集合的根节点的父节点

4.合并代码
static void merge(int u, int v)
{
	int x = find(u);
	int y = find(v);
	if(x == y)  //如果相同,就不合并了
		return;
	if(sz[x] < sz[y])
	{
		int temp =x;
		x = y;
		y= temp;
	}
	//把原来的值放进去
	undo_sz.push(new UndoObject(x,sz[x]));
	//存完以后,改掉
	sz[x] += sz[y];
	//把原来的值放进去
	undo_fa.push(new UndoObject(y, fa[y]));
	//存完以后,改掉
	fa[y]= x;
}

这是并查集中的合并(连接)操作的实现,用于将两个节点所属的集合合并成一个集合。函数merge的具体步骤如下:

  1. 使用find函数找到节点u所属集合的根节点x和节点v所属集合的根节点 y。
    1. 如果x和y相等,说明节点u和节点v已经在同一个集合中,无需合并,直接返回。
    2. 如果 sz[x]< sz[y],即集合 x的大小小于集合 y的大小,那么交换x和 y,确保较大的集合成为合并后的集合的根节点。
  2. 记录合并前的状态信息,将x的大小siz[x]和y的父节点 fa[y]分别入栈 undo_sz 和undo fa.
  3. 更新集合大小和父节点信息,将集合y合并到集合x中。
    这个合并操作不仅将两个集合合并,还通过栈undo_sz和 undo_fa 记录了合并前的状态信息,以便后续可能的撤销操作。这种记录状态的设计可以在撤销时还原到之前的状态,使得操作更加灵活。
5.撤销代码
void undo()
{
	fa[undo_fa.top().pos]=undo_fa.top().val;
	undo_fa.pop();
	siz[undo_sz.top().pos]=undo_sz.top().val;
	undo_sz.pop();
}

这是用于撤销最近一次连接操作的函数 undo的实现。该函数通过栈undo_ fa和undo_sz 中记录的信息,将最近一次连接操作的状态还原到连接之前的状态。具体步如下:

  1. 从 undo_fa 栈中取出最近一次连接操作前的状态信息,包括位置 pos 和父节点的值 val。然后,将城市 pos 的父节点更新为val。
  2. 从 undo_sz 栈中取出最近一次连接操作前的状态信息,包括集合的根节点位置pos 和集合的大小 val。然后,将集合 pos 的大小更新为 val。
  3. 分别从 undo_fa 和 undo_sz 栈中弹出这些信息;确保下一次 undo 操作不会再次撤销同一次连接操作。
    这个函数实现了撤销操作,可以在需要的时候将并查集的状态回滚到之前的状态

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/479011.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Python螺旋折线蓝桥杯(来源lanqiao.cn 题目176) 时间超限

题目描述 如图所示的螺旋折线经过平面上所有整点恰好一次。 对于整点(X, Y)&#xff0c;我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。 例如dis(0, 1)3, dis(-2, -1)9 给出整点坐标(X, Y)&#xff0c;你能计算出dis(X, Y)吗&#xff1f; 输入格式 …

【Unity】层(Layer)详解

1.什么是Layer? 我们在做游戏开发的时候&#xff0c;尤其是场景比较复杂的时候&#xff0c;我们就需要使用Layer来分类。 比如&#xff1a; 排除不被灯光照亮的Layer 射线检测特定的 Layer 摄像机只能看到某些 Layer 对象之间的碰撞检测 Layer … 2.添加Layer ①在Inspecto…

GZ083 产品艺术设计赛题第十

全国职业院校技能大赛 产品艺术设计赛项赛题十 赛项名称 产品艺术设计 英语名称 Product Art Design 赛项编号 GZ083 归属产业 数字产业 任务名称 “绣羽鸣春”鸟形象主题文具收纳袋设计 赛项组别 中职组 高职组 □学生组 □教师组 □师生联队试点赛项 R学生组 …

Echarts地图之——如何给地图添加背景图片

上期我们已经给地图添加了一个阴影3d的效果&#xff0c;但是背景纯色的感觉还是不怎么好看&#xff0c;希望能给地图加个背景图。 一般来说给地图加背景图的情况较少&#xff0c;加个渐变色或者根据数据的情况给某些省份设置不一样的背景色&#xff0c;这样的做法是比较多的。…

C++关键字:const

文章目录 一、const的四大作用1.修饰 变量、数组2.修饰 函数的形参、修饰 引用 (最常用&#xff09;3.修饰 指针&#xff1a;常量指针、指针常量 、只读指针4.修饰 类的成员函数、修饰 类的对象 一、const的四大作用 1.修饰 变量、数组 1.const修饰变量&#xff1a; 被const修…

MySQL 如何修改密码

** MySQL 如何修改 root 密码 ** 一、如果 mysql 未设置 root 初始密码&#xff0c;可直接登录&#xff0c;修改密码。 mysql -u root -p --- 连接权限数据库 mysql> use mysql; --- 低版本 mysql 5.x mysql> update user set passwordpassword(123) where userro…

Type-C一拖多智能快充线方案

一拖二快充线PD芯片&#xff1a;技术革新与充电效率的提升 在移动设备日益普及的今天&#xff0c;充电技术的革新显得尤为重要。一拖二快充线PD芯片作为充电技术领域的一项创新成果&#xff0c;不仅提高了充电效率&#xff0c;还满足了用户多设备同时充电的需求。本文将深入探…

Python 三维可视化库之visualpython使用详解

概要 在科学计算和数据可视化领域,交互式三维可视化是一种强大的工具,可以帮助研究人员直观地探索数据和模拟结果。Python 的 visualpython 库就是这样一款强大的工具,它提供了丰富的功能和易用的接口,可以让用户轻松创建交互式的三维场景,展示复杂的科学计算结果。本文将…

springboot项目yml文件中${}的使用

作用 项目启动时可以灵活的通过修改环境变量来替换配置中的值&#xff0c;如果没有传该环境变量时&#xff0c;就是用默认值&#xff1b; 格式&#xff1a;${自定义参数名:默认值} 代码举例&#xff0c;已开启应用的端口号为例&#xff1a; server: port: ${SERVER_PORT:9…

Python代码实现Excel表格转HTML文件

Excel工作簿是常用的表格格式&#xff0c;广泛用于组织、分析及展示数据。Excel文件通常需要专门的文档阅览器进行查看。如果我们想要以更兼容的方式展示Excel表格&#xff0c;可以将其转换为HTML格式&#xff0c;使其能够在各种浏览器中直接进行查看。同时&#xff0c;将Excel…

[VulnHub靶机渗透] Kioptrix1.2

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【Java、PHP】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收…

腾讯在GDC 2024展示GiiNEX AI游戏引擎现已投入《元梦之星》中开发使用,展示强大AIGC能力

在近日举行的GDC 2024游戏开发者大会上&#xff0c;腾讯揭开了其AI Lab团队精心打造的GiiNEX AI游戏引擎的神秘面纱。这款引擎依托先进的生成式AI和决策AI技术&#xff0c;为游戏行业带来了革命性的变革。 相关阅读&#xff1a;腾讯游戏出品&#xff01;腾讯研效AIGC&#xff…

今天聊聊Docker

在数字化时代&#xff0c;软件应用的开发和部署变得越来越复杂。环境配置、依赖管理、版本控制等问题给开发者带来了不小的挑战。而Docker作为一种容器化技术&#xff0c;正以其独特的优势成为解决这些问题的利器。本文将介绍Docker的基本概念、优势以及应用场景&#xff0c;帮…

惠普EliteBook使用VirtualBox安装ISO镜像

实验环境 虚拟机软件&#xff1a;Oracle VM VirtualBox 6.1.16镜像文件&#xff1a;CentOS-7-x86_64-Minimal-2009.iso笔记本&#xff1a;惠普EditBook操作系统&#xff1a;Window10 BIOS开启虚拟化技术 一遍笔记本都不会开启虚拟化技术的&#xff0c;但是在window里使用虚拟…

通过更新路书当前坐标下marker的icon来展示沿途的风景

通过更新路书当前坐标下marker的icon来展示沿途的风景 1.效果图2.[工程链接](https://download.csdn.net/download/m0_61864577/88978866)3.需修改地方: 本文演示了如何通过百度地图的路书功能,展示途经的风景。定时缩放,既有全局路径,又有当前位置和运动轨迹;可以显示当前坐标…

使用zabbix自动发现规则监控oracle分区表的分区键的合法

一、 创建从数据库查询原始数据脚本 编写脚本query_table.sh vim query_table.sh #!/bin/bash temp_outfile"/tmp/table.source" outfile"/tmp/table.txt" source /home/oracle/.bash_profilesqlplus -s zabbix/zabbix>${temp_outfile}<<EOF c…

Oracle数据库——单行函数1(字符函数和数字函数)

单行函数 操作数据对象接受参数返回一个结果只对一行进行变换每行返回一个结果可以转换数据类型可以嵌套参数可以是一列或一个值一、字符函数 1.大小写控制函数

使用OpenCV将图片切割成小图 及图片拼接(附python代码)

文章目录 1. 图片切割2. 图片拼接3. AcknowledgmentReference 要分割的图片如下&#xff1a; 1. 图片切割 思路也比较简单&#xff0c;代码注释比较详细&#xff0c;看代码就行。 from cv2 import cv2 import numpy as np import ospic_path .jpg # 分割的图片的位置 pic_ta…

离散型工业生产制造MES管理系统解决方案

一、核心优势 1、业务场景高适配 ①配置好程度高,可适应不同的业务场景。 ②业务功能灵活可配,可根据客户需求及时调整。 2、功能覆盖全周期 产品功能覆盖面广,能够实现从来料管理到销售出库整个产品生命周期管控。 3、触点互联降成本 能将相关的设备集成至MES中来,实现与设…

【Web】浅聊Jackson序列化getter的利用——POJONode

目录 核心速览 原理分析 EXP TemplatesImpl利用 SignedObject利用 核心速览 writeValueAsString是jackson序列化自带的入口&#xff0c;在调用该方法的过程中将会通过遍历的方法将bean对象中的所有的属性的getter方法进行调用 下面介绍如下利用链&#xff1a; BadAttrib…