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

【数据结构】 并查集 + 路径压缩与按秩合并 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 N10 M ≤ 20 M \le 20 M20

对于 35 % 35\% 35% 的数据, N ≤ 100 N \le 100 N100 M ≤ 1 0 3 M \le 10^3 M103

对于 50 % 50\% 50% 的数据, 1 ≤ N ≤ 1 0 4 1\le N \le 10^4 1N104 1 ≤ M ≤ 2 × 1 0 5 1\le M \le 2\times 10^5 1M2×105

对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 2 × 1 0 5 1\le N\le 2\times 10^5 1N2×105 1 ≤ M ≤ 1 0 6 1\le M\le 10^6 1M106 1 ≤ X i , Y i ≤ N 1 \le X_i, Y_i \le N 1Xi,YiN 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

目录 前言模板朴素实现路径压缩按秩合并按树高为秩按节点数为秩 总结 前言 并查集的基本实现通常使用森林来表示不同的集合&#xff0c;每个集合用一棵树表示&#xff0c;树的每个节点有一个指向其父节点的指针。 如果一个节点是它自己的父节点&#xff0c;那么它就是该集合的代…...

无耳科技 Solon v3.0.7 发布(2025农历新年版)

Solon 框架&#xff01; Solon 框架由杭州无耳科技有限公司&#xff08;下属 Noear 团队&#xff09;开发并开源。是新一代&#xff0c;面向全场景的 Java 企业级应用开发框架。从零开始构建&#xff08;非 java-ee 架构&#xff09;&#xff0c;有灵活的接口规范与开放生态。…...

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”的神经网络结构&#xff0c;该结构在一个基数组&#xff08;cardinal group&#xff09;内进行操作。基数组通常指的是在神经网络中处理的一组特征或通道。图中展示了如何通过一系列操作来实现对输入特征的注意力机制。 以下是图中各部…...

澳洲硕士毕业论文写作中如何把握主题

每到毕业季时&#xff0c;澳洲硕士毕业论文写作是留学生学业的头等大事。但是经常有留学生在澳洲毕业论文写作过程中会遇到写了一半&#xff0c;但是不知道应该如何继续下去的问题。有时候是在literature review的部分就越写越觉得偏离了方向&#xff0c;有时候是在数据收集阶段…...

STM32 LED呼吸灯

接线图&#xff1a; 这里将正极接到PA0引脚上&#xff0c;负极接到GND&#xff0c;这样就高电平点亮LED&#xff0c;低电平熄灭。 占空比越大&#xff0c;LED越亮&#xff0c;占空比越小&#xff0c;LED越暗 PWM初始化配置 输出比较函数介绍&#xff1a; 用这四个函数配置输…...

Java数据库操作指南:快速上手JDBC【学术会议-2025年数字化教育与信息技术(DEIT 2025】

大会官网&#xff1a;www.ic-deit.org 前言 在现代企业应用中&#xff0c;数据库是数据存储和管理的重要组成部分。Java作为一种广泛使用的编程语言&#xff0c;提供了多种方式与数据库进行交互。本文将介绍 JDBC&#xff08;Java Database Connectivity&#xff09;&#x…...

2024年个人总结

序 照例&#xff0c;每年都有的个人年度总结来了&#xff0c;看了很多其他大佬的总结&#xff0c;感觉自己的2024过于单薄&#xff0c;故事也不太丰满&#xff0c;自己就回去比较&#xff0c;自己哪里做的不好 &#xff1f;但后来发现已经进入了一个思维误区。 年度总结年度总结…...

GitHub 仓库的 Archived 功能详解:中英双语

GitHub 仓库的 Archived 功能详解 一、什么是 GitHub 仓库的 “Archived” 功能&#xff1f; 在 GitHub 上&#xff0c;“Archived” 是一个专门用于标记仓库状态的功能。当仓库被归档后&#xff0c;它变为只读模式&#xff0c;所有的功能如提交代码、创建 issue 和 pull req…...

LeetCode:56.合并区间

跟着carl学算法&#xff0c;本系列博客仅做个人记录&#xff0c;建议大家都去看carl本人的博客&#xff0c;写的真的很好的&#xff01; 代码随想录 LeetCode&#xff1a;56.合并区间 以数组 intervals 表示若干个区间的集合&#xff0c;其中单个区间为 intervals[i] [starti,…...

Vue演练场基础知识(七)插槽

为学习Vue基础知识&#xff0c;我动手操作通关了Vue演练场&#xff0c;该演练场教程的目标是快速体验使用 Vue 是什么感受&#xff0c;设置偏好时我选的是选项式 单文件组件。以下是我结合深入指南写的总结笔记&#xff0c;希望对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 网关地址是否相等&#xff0c;包括前缀 实现步骤 解析 IPv6 地址&#xff1a;使用 inet_pton 将字符串形式的 IPv6 地址转换为二进制形式。解析前缀长度&#xff1a;从地址字符串中提取前缀长度&#xff08;如 /64&#xf…...

【uniapp】uniapp使用java线程池

标题 由于js是性能孱弱的单线程语言&#xff0c;只要在渲染中执行了一些其他操作&#xff0c;会中断渲染&#xff0c;导致页面卡死&#xff0c;卡顿&#xff0c;吐司不消失等问题。在安卓端可以调用java线程池&#xff0c;把耗时操作写入线程池里面&#xff0c;优化性能。 实…...

面试题-Java集合框架

前言 Java集合框架&#xff08;Java Collections Framework&#xff09;是Java平台提供的一套用于表示和操作集合的统一架构。它位于java.util包中&#xff0c;并且自Java 1.2&#xff08;也称为Java 2平台&#xff0c;标准版&#xff0c;即Java SE 2&#xff09;起成为Java平…...

Java基础教程(007):方法的重载与方法的练习

文章目录 6.5 方法的重载6.6 方法练习数组遍历数组最大值 6.5 方法的重载 在 Java 中&#xff0c;方法的重载是指在同一个类中定义多个方法&#xff0c;这些方法具有相同的名称&#xff0c;但参数列表不同。方法的重载是一种实现多态的方式&#xff0c;允许一个方法名以不同的…...

【ESP32】ESP-IDF开发 | WiFi开发 | TCP传输控制协议 + TCP服务器和客户端例程

1. 简介 TCP&#xff08;Transmission Control Protocol&#xff09;&#xff0c;全称传输控制协议。它的特点有以下几点&#xff1a;面向连接&#xff0c;每一个TCP连接只能是点对点的&#xff08;一对一&#xff09;&#xff1b;提供可靠交付服务&#xff1b;提供全双工通信&…...

npm cnpm pnpm npx yarn的区别

npm、cnpm、pnpm、npx、yarn 这几个工具都与 Node.js 项目的包管理和命令执行相关&#xff0c;它们的区别具体如下&#xff1a; 本质与功能定位 npm&#xff1a;是 Node.js 官方的包管理工具&#xff0c;提供了安装、卸载、更新、发布等全方位的包管理功能&#xff0c;还能通…...

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…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

《Docker》架构

文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器&#xff0c;docker&#xff0c;镜像&#xff0c;k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...

在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7

在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤&#xff1a; 第一步&#xff1a; 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为&#xff1a; // 改为 v…...