数据结构 并查集
作用
快速的处理以下问题:【近乎O(1)的时间完成】
1.将两个集合合并
2.询问两个元素是否在一个集合中
用树的形式维护集合
基本原理
每一个集合用一棵树表示
每一个集合的编号就是根结点的编号,对于每一个结点,都存储其父结点,p[x]表示x的父结点,即p[x]=a表示编号为x的结点的父结点的编号为a
求某个点属于哪个集合时,就先找其父结点,如果其父结点不是根结点,那么就继续找其父结点的父结点,直到找到其根结点为止
问题1
如何判断树根:if(p[x]==x)
问题2
如何求x的集合编号:while(p[x]!=x) x=p[x];【只要x不是树根,就一直往上走,直到找到树根为止】
该步骤时间复杂度仍然很高,需要进行以下优化:
路径压缩:一旦找到根结点,就会把整个路径上所有点都指向根结点。【基本O(1)】
安秩合并【一般不用】
问题3
如何合并两个集合:px是x集合的集合编号【即x集合的根节点的编号是px】,py是y集合的集合编号【即y集合的根节点的编号是py】 p[px]=py或p[py]=px
代码实现
int find(int x) {//返回x所在集合的编号+路径压缩
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
例题——合并集合
一共有n个数,编号是1~n,最开始每个数各自在一个集合中。
现在要进行m个操作,操作共有两种:
“M a b”,将编号为a和b的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;
“Q a b”,询问编号为a和b的两个数是否在同一个集合中;
输入格式
第一行输入整数n和m。
接下来m行,每行包含一个操作指令,指令为“M a b”或“Q a b”中的一种。
输出格式
对于每个询问指令”Q a b”,都要输出一个结果,如果a和b在同一集合内,则输出“Yes”,否则输出“No”。
每个结果占一行。
数据范围
1≤n,m≤105
输入样例
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例
Yes
No
Yes
代码
#include<iostream>
using namespace std;
const int N = 100010;
int p[N];//存储父结点
int n, m;
int find(int x) {//返回x所在集合的编号+路径压缩
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1;i <= n;i++)
p[i] = i;
while (m--) {
char op[2];//因为在使用scanf进行读取时,若读取单个字符会读取到空格、回车等其他字符,使用scanf读取字符串时可忽略空格、回车等其他字符
int a, b;
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'M')
p[find(a)] = find(b);//合并
//find(a)返回a的祖宗结点,find(b)返回b的祖宗结点,让a的祖宗结点的父结点等于b的祖宗结点
else {
if (find(a) == find(b))
puts("Yes");
else
puts("No");
}
}
return 0;
}
例题——连通块中点的数量
给定一个包含n个点(编号为1~n)的无向图,初始时图中没有边。
现在要进行m个操作,操作共有三种:
“C a b”,在点a和点b之间连一条边,a和b可能相等;
“Q1 a b”,询问点a和点b是否在同一个连通块中,a和b可能相等;
“Q2 a”,询问点a所在连通块中点的数量;
输入格式
第一行输入整数n和m。
接下来m行,每行包含一个操作指令,指令为“C a b”,“Q1 a b”或“Q2 a”中的一种。
输出格式
对于每个询问指令”Q1 a b”,如果a和b在同一个连通块中,则输出“Yes”,否则输出“No”。
对于每个询问指令“Q2 a”,输出一个整数表示点a所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤10^5
输入样例
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例
Yes
2
3
代码
#include<iostream>
using namespace std;
const int N = 100010;
int p[N], size1[N];//存储父结点
int n, m;
int find(int x) {//返回x所在集合的编号+路径压缩
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1;i <= n;i++) {
p[i] = i;
size1[i] = 1;
}
while (m--) {
char op[5];
int a, b;
scanf("%s", op);
if (op[0] == 'C') {
scanf("%d%d", &a, &b);
if (find(a) == find(b))
continue;
//特判:如果两个数已经在一个集合,就不用再次合并,不然会使得元素中的元素个数翻倍
size1[find(b)] += size1[find(a)];//b中元素数量为其本身加上a中元素数量
p[find(a)] = find(b);//合并,将a合并到b中
}
else if (op[1] == '1') {
scanf("%d%d", &a, &b);
if (find(a) == find(b))
puts("Yes");
else
puts("No");
}
else {
scanf("%d", &a);
printf("%d\n", size1[find(a)]);
}
}
return 0;
}
相关文章:
数据结构 并查集
作用 快速的处理以下问题:【近乎O(1)的时间完成】 1.将两个集合合并 2.询问两个元素是否在一个集合中 用树的形式维护集合 基本原理 每一个集合用一棵树表示 每一个集合的编号就是根结点的编号,对于每一个结点,都存储其父结点…...
算法通关村第十六关黄金挑战——求滑动窗口中的最大值(滑动窗口与堆方法、双端队列法和直接比较法)
大家好,我是怒码少年小码。 今天这篇就讲一道题目,不难😎,但是一定要学会自己思考。 滑动窗口最大值 LeetCode 239:给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。…...
常见树种(贵州省):009楠木、樟木、桂木种类
摘要:本专栏树种介绍图片来源于PPBC中国植物图像库(下附网址),本文整理仅做交流学习使用,同时便于查找,如有侵权请联系删除。 图片网址:PPBC中国植物图像库——最大的植物分类图片库 一、楠木 …...
全志H616开发版
开发板介绍: 二、开发板刷机 SDFormatter TF卡的格式化工具、Win32Diskimager 刷机工具 刷机镜像为:Orangepizero2_2.2.0_ubuntu_bionic_desktop_linux4.9.170.img 使用MobaXterm_Personal_20.3连接使用 网络配置:nmcli dev wifi 命令接入网…...
【Spring boot】RedisTemplate中String、Hash、List设置过期时间
文章目录 前言Redis中String设置时间的方法Redis中Hash和List设置时间的方法Redis中Hash的put、putAll、putIfAbsent区别 前言 时间类型:TimeUnit import java.util.concurrent.TimeUnit;TimeUnit.SECONDS:秒 TimeUnit.MINUTES:分 TimeUnit.HOURS&…...
Nosql之redis概述及基本操作
关系数据库与非关系型数据库概述 关系型数据库 关系型数据库是一个结构化的数据库,创建在关系模型(二维表格模型)基础上,一般面向于记录。SQL语句(标准数据查询语言)就是一种基于关系型数据库的语言,用于执行对关系型…...
使ros1和ros2的bag一直互通
很多文章都是先source ros1 然后source ros2,再play bag source /opt/ros/noetic/setup.bash source /opt/ros/foxy/setup.bash ros2 bag play -s rosbag_v2 kitti_raw00.bag 但实测会出问题: 为使ros1和ros2的bag一直互通 sudo apt update sudo apt install ros-foxy-ro…...
【正点原子 linux 驱动编程】
在此声明,正用点编的说明书真的拉,丝毫不具备兼容性。。比如linux的第一个实验,其中包含的 unregister_chrdev_region 函数,fileoperation 结构体等均来自 <linux/fs.h> 文件,搞不懂,他们方ide.h&…...
使用Python的turtle模块绘制玫瑰花图案(含详细Python代码与注释)
1.1引言 turtle模块是Python的标准库之一,它提供了一个绘图板,让我们可以在屏幕上绘制各种图形。通过使用turtle,我们可以创建花朵、叶子、复杂的图案等等。本博客将介绍如何使用turtle模块实现绘制图形的过程,并展示最终结果。 …...
Redis学习笔记14:基于spring data redis及lua脚本ZSET有序集合实现环形结构案例及lua脚本如何发送到redis服务器
案例实现目标,一、实现一个环形结构,环形结构上节点有一个阀值threshold,超过阀值则移除分数score最低的成员,不足则将当前成员添加进环中,且确保成员不可重复;二、每次访问环中的数据都需要刷新key的过期时间…...
openssl C++研发之pem格式处理详解
一、PEM_writeXXX和EM_write_bio_XXX 在OpenSSL的crypto/pem.h头文件中,PEM_write_XXXX和PEM_write_bio_XXXX系列函数用于将特定类型的数据写入文件或BIO(内存缓冲区)中,其中XXXX代表不同的数据类型。 这些函数的使用方式相似&a…...
【教3妹学编辑-mysql】详解数据库三大范式
什么是范式 简单地理解就是:数据库设计时遵循的规范 三大范式 数据库三大范式包含:1、第一范式(1NF);2、第二范式(2NF);3、第三范式(3NF)。其中,第一范式(1NF)的要求是属性不可分割,第二范式(2NF)的要求是…...
【计算机网络笔记】路由算法之链路状态路由算法
系列文章目录 什么是计算机网络? 什么是网络协议? 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能(1)——速率、带宽、延迟 计算机网络性能(2)…...
读像火箭科学家一样思考笔记04_第一性原理(下)
1. 来自无形规则的阻力 1.1. 无形规则 1.1.1. 僵化成规则的不必要习惯和行为 1.1.2. 不像有形的书面规则 1.1.2.1. 书面规则出现在标准操作流程中,可以修改或删除 1.1.3. 成文的规则可能会抗拒变革,但无形规则却更加顽固 1.1.4. 我们为强加在自己身…...
开源集群管理系统对比分析:Kubernetes 与 Apache Mesos
集群管理系统是关键的软件解决方案,可以在互连机器网络中有效分配和利用计算资源。毫无疑问,它们通过确保可扩展性、高可用性和有效的资源管理在现代计算中发挥着至关重要的作用,这使得它们对于运行复杂的应用程序、管理数据中心以及进一步增…...
matlab 坡度滤波算法地面分割
目录 一、算法原理1、实现流程2、参考文献二、代码实现三、结果展示四、测试数据一、算法原理 1、实现流程 1、格网示意图 2、计算格网行列数 公式中的特殊符号为向上取整,...
【腾讯云 HAI域探秘】高性能服务器引领AI革新浪潮:从AI绘画、知识问答到PyTorch图像分类、视频检测的全方位探索
目录 1 HAI(高性能应用服务)简介2 HAI的应用场景2.1 HAI在AI作画中的灵活性与效率2.2 深入探索LLM语言模型的应用与性能2.3 HAI支持的AI模型开发环境与工具 3 基于stable difussio的AI 绘画应用实践3.1 使用AI模型中的stable diffusion模型服务3.2 设置和…...
【Java】ExcelWriter自适应宽度工具类(支持中文)
工具类 import org.apache.poi.ss.usermodel.Cell; import org.apache.poi.ss.usermodel.CellType; import org.apache.poi.ss.usermodel.Row; import org.apache.poi.ss.usermodel.Sheet;/*** Excel工具类** author xiaoming* date 2023/11/17 10:40*/ public class ExcelUti…...
C++二分查找算法:132模式枚举3简洁版
本文涉及的基础知识点 二分查找算法合集 本题不同解法 包括题目及代码C二分查找算法:132 模式解法一枚举3C二分查找算法:132 模式解法二枚举2代码简洁C二分查找算法:132 模式解法三枚举1性能最佳C单调向量算法:132 模式解法三枚…...
Map 和 WeakMap:JavaScript 中的键值对集合
JavaScript 是一种动态、弱类型的脚本语言,经常用于构建现代 Web 应用程序。在编写 JavaScript 代码时,我们经常需要使用各种数据结构来存储和管理数据。其中,Map 和 WeakMap 就是两个非常有用的数据结构,它们分别提供了用于存储键…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
