【数据结构】 并查集 + 路径压缩与按秩合并 python
目录
- 前言
- 模板
- 朴素实现
- 路径压缩
- 按秩合并
- 按树高为秩
- 按节点数为秩
- 总结
前言
并查集的基本实现通常使用森林来表示不同的集合,每个集合用一棵树表示,树的每个节点有一个指向其父节点的指针。
如果一个节点是它自己的父节点,那么它就是该集合的代表(称为根节点)。
模板
P3367 【模板】并查集 https://www.luogu.com.cn/problem/P3367
题目描述
如题,现在有一个并查集,你需要完成合并和查询操作。
输入格式
第一行包含两个整数 N , M N,M N,M ,表示共有 N N N 个元素和 M M M 个操作。
接下来 M M M 行,每行包含三个整数 Z i , X i , Y i Z_i,X_i,Y_i Zi,Xi,Yi 。
当 Z i = 1 Z_i=1 Zi=1 时,将 X i X_i Xi 与 Y i Y_i Yi 所在的集合合并。
当 Z i = 2 Z_i=2 Zi=2 时,输出 X i X_i Xi 与 Y i Y_i Yi 是否在同一集合内,是的输出
Y ;否则输出 N 。
输出格式
对于每一个 Z i = 2 Z_i=2 Zi=2 的操作,都有一行输出,每行包含一个大写字母,为 Y 或者 N 。
**样例输入 **
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
样例输出
N
Y
N
Y
提示
对于 15 % 15\% 15% 的数据, N ≤ 10 N \le 10 N≤10, M ≤ 20 M \le 20 M≤20。
对于 35 % 35\% 35% 的数据, N ≤ 100 N \le 100 N≤100, M ≤ 1 0 3 M \le 10^3 M≤103。
对于 50 % 50\% 50% 的数据, 1 ≤ N ≤ 1 0 4 1\le N \le 10^4 1≤N≤104, 1 ≤ M ≤ 2 × 1 0 5 1\le M \le 2\times 10^5 1≤M≤2×105。
对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 2 × 1 0 5 1\le N\le 2\times 10^5 1≤N≤2×105, 1 ≤ M ≤ 1 0 6 1\le M\le 10^6 1≤M≤106, 1 ≤ X i , Y i ≤ N 1 \le X_i, Y_i \le N 1≤Xi,Yi≤N, Z i ∈ { 1 , 2 } Z_i \in \{ 1, 2 \} Zi∈{1,2}。
朴素实现
code:
# 在集合中查找元素的根节点
def find(x):if x != pre[x]:return find(pre[x])return x# 将两个集合合并为一个集合
def union(x, y, pre):x_root = find(x)y_root = find(y)pre[x_root] = y_rootn, m = map(int, input().split())
pre = [0] * (n + 1)
for i in range(n):pre[i] = i # 初始化
for _ in range(m):op, x, y = map(int, input().split())if op == 1:union(x, y, pre)else:if find(x) == find(y):print('Y')else:print('N')

事实证明:我们需要进行时间上的优化
路径压缩
由于在查询过程中只关心根结点是什么,所以我们可以在在集合在查找元素的同时,把集合中所有的元素都直接指向根节点,减少查找的时间
示例code
def find(x):if pre[x] != x:pre[x] = find(pre[x]) # 在回溯时进行路径压缩return pre[x]
tips:可能会破坏原本的结构
按秩合并
之前我们在合并时,是随机合并两个集合
虽然都能得到正确的结果,但存在时间复杂度的差异
怎样降低时间复杂度呢?
通过按秩合并(启发式合并)
“秩”可以理解为树的高度或树的节点数 这两种方式
在合并两棵树时,总是把较矮的树挂到较高的树上,节点较小的树挂在节点较多的树上
这种策略有助于保持树的平衡,从而降低查找操作的时间复杂度。
怎么实现?用一个数组记录每个集合的高度或节点数
按树高为秩
示例:
# 将两个集合合并为一个集合
def union(x, y):x_root = find(x)y_root = find(y)if x_root != y_root:# 谁高,谁就作为根节点if rank[x_root] > rank[y_root]:pre[y_root] = x_rootelif rank[x_root] < rank[y_root]:pre[x_root] = y_rootelse:pre[x_root] = y_rootrank[y_root] += 1
# 合并是把小的树直接接到根节点上,所以只有两颗树的高度相等的时候合并后高度才会增加
按节点数为秩
示例:
# 将两个集合合并为一个集合
def union(x, y):x_root = find(x)y_root = find(y)if x_root != y_root:# 谁的节点数多,谁就作为根节点if size[x_root] > size[y_root]:pre[y_root] = x_rootsize[x_root] += size[y_root]else:pre[x_root] = y_rootsize[y_root] += size[x_root]
题解code1(路径压缩+按节点数为秩合并):
# 在集合中查找元素的根节点
def find(x):global preif pre[x] != x:pre[x] = find(pre[x]) # 在回溯时进行路径压缩return pre[x]# 将两个集合合并为一个集合
def union(x, y):global pre, sizex_root = find(x)y_root = find(y)if x_root != y_root:# 谁的节点数多,谁就作为根节点if size[x_root] > size[y_root]:pre[y_root] = x_rootsize[x_root] += size[y_root]else:pre[x_root] = y_rootsize[y_root] += size[x_root]n, m = map(int, input().split())
pre = list(range(n + 1)) # 初始化pre数组
size = [1] * (n + 1) # 初始化size数组
for _ in range(m):op, x, y = map(int, input().split())if op == 1:union(x, y)else:if find(x) == find(y):print('Y')else:print('N')
路径压缩与按节点大小合并完全兼容
题解code2(按树高为秩合并):
# 在集合中查找元素的根节点
def find(x):global preif pre[x] != x:pre[x] = find(pre[x]) # 在回溯时进行路径压缩return pre[x]# 将两个集合合并为一个集合
def union(x, y):global pre, rankx_root = find(x)y_root = find(y)if x_root != y_root:# 谁高,谁就作为根节点if rank[x_root] > rank[y_root]:pre[y_root] = x_rootelif rank[x_root] < rank[y_root]:pre[x_root] = y_rootelse:pre[x_root] = y_rootrank[y_root] += 1
# 合并是把小的树直接接到根节点上,所以只有两颗树的高度相等的时候合并后高度才会增加n, m = map(int, input().split())
pre = list(range(n + 1)) # 初始化pre数组
rank = [1] * (n + 1) # 初始化rank数组
for _ in range(m):op, x, y = map(int, input().split())if op == 1:union(x, y)else:if find(x) == find(y):print('Y')else:print('N')
路径压缩不完全与按树高合并兼容,因为路径压缩可以改变树的高度。
总结
并查集(Union-Find 或 Disjoint Set Union, DSU)是一种数据结构,主要用于处理一些不相交集合的合并及查询问题。
如果有更多问题或需要进一步的帮助,可以在评论区留言讨论哦!
如果喜欢的话,请给博主点个关注 谢谢
相关文章:
【数据结构】 并查集 + 路径压缩与按秩合并 python
目录 前言模板朴素实现路径压缩按秩合并按树高为秩按节点数为秩 总结 前言 并查集的基本实现通常使用森林来表示不同的集合,每个集合用一棵树表示,树的每个节点有一个指向其父节点的指针。 如果一个节点是它自己的父节点,那么它就是该集合的代…...
无耳科技 Solon v3.0.7 发布(2025农历新年版)
Solon 框架! Solon 框架由杭州无耳科技有限公司(下属 Noear 团队)开发并开源。是新一代,面向全场景的 Java 企业级应用开发框架。从零开始构建(非 java-ee 架构),有灵活的接口规范与开放生态。…...
UART、I2C和SPI对比
UARTSPII2C英文Universal Asynchronous Receive/TransmitSerial Peripheral InterfaceInner Integrated Communication通讯速度115200、38400 bit/s高达100M bit/s 100k、400k、1M、3.4M bit/s时钟同/异步性时钟异步时钟同步时钟同步接线方式3线(Rx、Tx、GND) 4线(MISO、…...
Vue 响应式渲染 - 待办事项简单实现
Vue 渐进式JavaScript 框架 基于Vue2的学习笔记 - Vue 响应式渲染 - 待办事项简单实现 目录 待办事项简单实现 页面初始化 双向绑定的指令 增加留言列表设置 增加删除按钮 最后优化 总结 待办事项简单实现 页面初始化 对页面进行vue的引入、创建输入框和按钮及实例化V…...
ResNeSt: Split-Attention Networks论文学习笔记
这张图展示了一个名为“Split-Attention”的神经网络结构,该结构在一个基数组(cardinal group)内进行操作。基数组通常指的是在神经网络中处理的一组特征或通道。图中展示了如何通过一系列操作来实现对输入特征的注意力机制。 以下是图中各部…...
澳洲硕士毕业论文写作中如何把握主题
每到毕业季时,澳洲硕士毕业论文写作是留学生学业的头等大事。但是经常有留学生在澳洲毕业论文写作过程中会遇到写了一半,但是不知道应该如何继续下去的问题。有时候是在literature review的部分就越写越觉得偏离了方向,有时候是在数据收集阶段…...
STM32 LED呼吸灯
接线图: 这里将正极接到PA0引脚上,负极接到GND,这样就高电平点亮LED,低电平熄灭。 占空比越大,LED越亮,占空比越小,LED越暗 PWM初始化配置 输出比较函数介绍: 用这四个函数配置输…...
Java数据库操作指南:快速上手JDBC【学术会议-2025年数字化教育与信息技术(DEIT 2025】
大会官网:www.ic-deit.org 前言 在现代企业应用中,数据库是数据存储和管理的重要组成部分。Java作为一种广泛使用的编程语言,提供了多种方式与数据库进行交互。本文将介绍 JDBC(Java Database Connectivity)&#x…...
2024年个人总结
序 照例,每年都有的个人年度总结来了,看了很多其他大佬的总结,感觉自己的2024过于单薄,故事也不太丰满,自己就回去比较,自己哪里做的不好 ?但后来发现已经进入了一个思维误区。 年度总结年度总结…...
GitHub 仓库的 Archived 功能详解:中英双语
GitHub 仓库的 Archived 功能详解 一、什么是 GitHub 仓库的 “Archived” 功能? 在 GitHub 上,“Archived” 是一个专门用于标记仓库状态的功能。当仓库被归档后,它变为只读模式,所有的功能如提交代码、创建 issue 和 pull req…...
LeetCode:56.合并区间
跟着carl学算法,本系列博客仅做个人记录,建议大家都去看carl本人的博客,写的真的很好的! 代码随想录 LeetCode:56.合并区间 以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] [starti,…...
Vue演练场基础知识(七)插槽
为学习Vue基础知识,我动手操作通关了Vue演练场,该演练场教程的目标是快速体验使用 Vue 是什么感受,设置偏好时我选的是选项式 单文件组件。以下是我结合深入指南写的总结笔记,希望对Vue初学者有所帮助。 文章目录 十五. 插槽插槽…...
进程池的制作(linux进程间通信,匿名管道... ...)
目录 一、进程间通信的理解 1.为什么进程间要通信 2.如何进行通信 二、匿名管道 1.管道的理解 2.匿名管道的使用 3.管道的五种特性 4.管道的四种通信情况 5.管道缓冲区容量 三、进程池 1.进程池的理解 2.进程池的制作 四、源码 1.ProcessPool.hpp 2.Task.hpp 3…...
【Linux】Linux C比较两个 IPv6 网关地址是否相等,包括前缀
功能说明 在 Linux 环境下使用 C 语言比较两个 IPv6 网关地址是否相等,包括前缀 实现步骤 解析 IPv6 地址:使用 inet_pton 将字符串形式的 IPv6 地址转换为二进制形式。解析前缀长度:从地址字符串中提取前缀长度(如 /64…...
【uniapp】uniapp使用java线程池
标题 由于js是性能孱弱的单线程语言,只要在渲染中执行了一些其他操作,会中断渲染,导致页面卡死,卡顿,吐司不消失等问题。在安卓端可以调用java线程池,把耗时操作写入线程池里面,优化性能。 实…...
面试题-Java集合框架
前言 Java集合框架(Java Collections Framework)是Java平台提供的一套用于表示和操作集合的统一架构。它位于java.util包中,并且自Java 1.2(也称为Java 2平台,标准版,即Java SE 2)起成为Java平…...
Java基础教程(007):方法的重载与方法的练习
文章目录 6.5 方法的重载6.6 方法练习数组遍历数组最大值 6.5 方法的重载 在 Java 中,方法的重载是指在同一个类中定义多个方法,这些方法具有相同的名称,但参数列表不同。方法的重载是一种实现多态的方式,允许一个方法名以不同的…...
【ESP32】ESP-IDF开发 | WiFi开发 | TCP传输控制协议 + TCP服务器和客户端例程
1. 简介 TCP(Transmission Control Protocol),全称传输控制协议。它的特点有以下几点:面向连接,每一个TCP连接只能是点对点的(一对一);提供可靠交付服务;提供全双工通信&…...
npm cnpm pnpm npx yarn的区别
npm、cnpm、pnpm、npx、yarn 这几个工具都与 Node.js 项目的包管理和命令执行相关,它们的区别具体如下: 本质与功能定位 npm:是 Node.js 官方的包管理工具,提供了安装、卸载、更新、发布等全方位的包管理功能,还能通…...
debian12.9编译freeswitch1.10.12【默认安装】
服务器操作系统 cat /etc/os-release PRETTY_NAME"Debian GNU/Linux 12 (bookworm)" NAME"Debian GNU/Linux" VERSION_ID"12" VERSION"12 (bookworm)" VERSION_CODENAMEbookworm IDdebian HOME_URL"https://www.debian.org/&quo…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
