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

数据结构--并查集

一、并查集的概念

并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题。常常在使用中以森林来表示。

最裸并查集:

  1. 合并元素a和元素b 所在的集合。
  2. 查询元素a和元素b 是否属于同一组。是否在一个集合当中 ,近乎 O(1) 时间内支持两个操作

在这里插入图片描述
分组和对应的例子

二、并查集的结构

并查集是树形结构。不过,不是二叉树。
每个元素对应一个节点,每个组对应一颗树。
在并查集中,哪个节点是哪个节点的父亲以及树的形状等信息不用关注,整体是树形结构才最重要

1. 初始化

每个元素初始化时,分别是每一个集合的根节点 p[x] = x
在这里插入图片描述

2. 合并

和下面图一样,从一个组的根向另一个组的跟连边,将两棵树变成 一颗树,也就是两个组变成一个组
在这里插入图片描述

3. 查询

为了查询两个节点是否同一组,只要沿着树向上走,查询根节点是否相同,根节点相同时同一组,否则不同组。如上图中 (2)(5)的根是 (1),而(7)的根是(6) 所以(2)和(5)是同一组,但是(2)和(7)不是同一组。

并查集实现的注意点

在树形数据结构中,如果发生退化情况(二叉树退化为一维链表),那么时间复杂度会变的很高。在并查集中,只需按照如下方法就可以避免退化。

  • 对于每棵树,记录树的高度(rank)
  • 合并时,如果两棵树的rank不同,那么rank小的向rank大的连边。

在这里插入图片描述
此外,通过路径压缩,可以使并查集更高效率。对于每个节点,一旦向上走到了一次根节点,就把这个点到父亲的边改成为直接连向根。
如需要查询(7),就可以直接将(7)连接到根上。
在这里插入图片描述
在此之上,不仅查询的节点,所有在查询过程中经过的所有节点,都可以直接连接到根上。再次查询时,就可以很快查询到根是谁了。
如下,将(2)(3)(4)(5)都连接到(1)中。
在这里插入图片描述
在使用这种化简方法时,为了简单起见,即使树的高度发生变换,也不再修改rank。

查并集的复杂度

加入两个优化后,查并集的效率非常高。对n个元素的查并集进行一次操作的复杂度为O(a(n))。在这里a(n)时阿克曼(Ackermann)函数的反函数。这要比O(log(n))还要快。

不过,这是“均摊复杂度”。并不是每次都满足,多次后,平均每次复杂度。

并查集的实现

Acwing 836 合并集合

#include <iostream>
using namespace std;const int N = 100010;int n, m;
int p[N];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];int a, b;scanf("%s%d%d", op, &a, &b);if(op[0] == 'M') p[find(a)] = find(b);else{if(find(a) == find(b)) puts("Yes");else puts("No");}}return 0;
}

在这里插入图片描述

相关文章:

数据结构--并查集

一、并查集的概念 并查集是一种树型的数据结构&#xff0c;用于处理一些不相交集合&#xff08;disjoint sets&#xff09;的合并及查询问题。常常在使用中以森林来表示。 最裸并查集&#xff1a; 合并元素a和元素b 所在的集合。查询元素a和元素b 是否属于同一组。是否在一个…...

Leetcode 224. 基本计算器

文章目录 题目代码&#xff08;10.1 首刷看解析&#xff09; 题目 Leetcode 224. 基本计算器 代码&#xff08;10.1 首刷看解析&#xff09; class Solution { public:int calculate(string s) {stack<int> sk; // 存储正负号sk.push(1);int sign 1;int res 0;int i…...

Linux基础命令汇总

用户管理 su 切换用户&#xff1a;su 用户名 logname 显示当前用户的登录用户名&#xff1a;logname useradd 创建用户&#xff1a;useradd 用户名创建用户时指定用户的主组&#xff1a;useradd -g 组名 用户名 usermod 添加附属组&#xff1a;usermod -G 组…...

JAVA 获得特定格式时间

0 背景 我们有时要获取时间&#xff0c;年月日时分秒周几&#xff0c;有时要以特定的格式出现。这时就要借助 SimpleDateFormat 或者 DateTimeFormatter。有时要某个月份有多少天需要借助 Calendar。所以有必要了解一些知识。 1 SimpleDateFormat simpledateFormat 线程不安全…...

问题: 视频颜色问题,偏绿

参考 什么是杜比视界&#xff1f; - https://www.youtube.com/watch?vldXDQ6VlC7g 【哈士亓说】07&#xff1a;HDR、杜比视界究竟是个啥&#xff1f;为什么这个视频还不是HDR视频&#xff1f; - https://www.youtube.com/watch?vrgb9Xg3cJns 正文 视频应该是 杜比视界 电…...

智能文字识别技术——AI赋能古彝文保护

前言 人工智能在古彝文古籍保护方面具有巨大的潜力和意义。通过数字化、自动化和智能化的手段&#xff0c;可以更好地保护和传承古彝文的文化遗产&#xff0c;促进彝族文化的传承和发展。 文章目录 前言一、古彝文是什么&#xff1f;1.1古彝文的背景1.2古彝文古籍保护背景 二、…...

Linux压缩和解压命令大全:tar、gzip和zip完整教程

文章目录 linux中的压缩和解压命令简介什么是压缩和解压为什么要使用压缩和解压命令压缩命令tar命令创建.tar文件压缩目录压缩多个文件或目录 gzip命令压缩文件压缩后删除原文件压缩整个目录 zip命令创建.zip文件压缩文件或目录设置压缩级别 解压命令tar命令解压.tar文件解压到…...

Vue3 reactive和ref详解

reactive Vue3.0中的reactive reactive 是 Vue3 中提供的实现响应式数据的方法。在 Vue2 中响应式数据是通过 defineProperty 来实现的&#xff0c;在 Vue3 中响应式数据是通过 ES6 的 Proxy来实现的。reactive 参数必须是对象 (json / arr)如果给 reactive 传递了其它对象 默…...

jvs-rules(规则引擎)和jvs智能bi(自助式数据分析)9.22更新内容

规则引擎更新功能 新增: 1.新增节点匹配筛选 用于做多个条件的数据筛选&#xff0c;以便将符合条件的数据传递给下一个节点进行处理&#xff0c;通常用于实现复杂的查询逻辑。 2.复合变量节点新增判断条件选项说明 用户可以根据自己的需求&#xff0c;为复合变量节点添加不…...

Leetcode算法题练习(一)

目录 一、前言 二、移动零 三、复写零 四、快乐数 五、电话号码的字母组合 六、字符串相加 一、前言 大家好&#xff0c;我是dbln&#xff0c;从本篇文章开始我就会记录我在练习算法题时的思路和想法。如果有错误&#xff0c;还请大家指出&#xff0c;帮助我进步。谢谢&…...

Xilinx FPGA 7系列 GTX/GTH Transceivers (5)-- Aurora 8b10b 信号传输实战--小试牛刀

第一节:Xilinx FPGA 7系列 GTX/GTH Transceivers (1)–了解了GTX硬件的基础知识 第二节:IBERT GTX --通过Ibert IP测试链路通信 第三节:aurora 8b10b single lane 4byte–学习官方历程 第四节:aurora 8b10b single lane 4byte–修改官方例子,发收递增数。 GTX/GTH Transc…...

第三章:最新版零基础学习 PYTHON 教程(第七节 - Python 运算符—Python 成员身份和身份运算符)

Python 提供了两个成员资格运算符来检查或验证值的成员资格。它测试序列(例如字符串、列表或元组)中的成员资格。 in 运算符: “in”运算符用于检查序列中是否存在字符/子字符串/元素。如果在序列中找到指定元素,则求值为 True,否则求值为 False。例如, CSDNforCSDN 中…...

【Java 基础篇】Java 注解详解

在 Java 编程中&#xff0c;注解&#xff08;Annotation&#xff09;是一种元数据&#xff0c;它提供了关于程序代码的额外信息。注解不直接影响程序的执行&#xff0c;但可以在运行时提供有关程序的信息&#xff0c;或者让编译器执行额外的检查。 本文将详细介绍 Java 注解的…...

MVVM框架下两窗口的消息传递

副窗口关闭的时候将bool类型传递出去 var message new CloseWindowMessage {MedicineView_DialogResult true }; //CloseWindowMessage是存储bool类型的标记类 Messenger.Default.Send(message); 主窗体中添加关闭处理的方法 private void HandleCloseWindowMessage(Clo…...

ROS2 从头开始​​:第6部分 - ROS2 中的 DDS,用于可靠的机器人通信

一、说明 在这篇文章中,我们将重点关注 ROS 2的通信栈DDS,其中这是介于管理节点通信与控制节点通信环节,是上位机决策体系与下位机的控制体系实现指令-执行-反馈的关键实现机制。 二、ROS工程的概念框架 现代机器人系统非常复杂,因为需要集成各种类型的传感器、执行器和其…...

WebSocket的那些事(6- RabbitMQ STOMP目的地详解)

目录 一、目的地类型二、Exchange类型目的地三、Queue类型目的地四、AMQ Queue类型目的地五、Topic类型目的地 一、目的地类型 在上节 WebSocket的那些事&#xff08;5-Spring STOMP支持之连接外部消息代理&#xff09;中我们已经简单介绍了各种目的地类型&#xff0c;如下图&…...

SQL SELECT 语句基础

在数字化的世界中,数据已经成为了一种无处不在的资源。从游戏开发到商业智能,数据分析都是不可或缺的一部分。SQL(结构化查询语言)是一种用于与数据库进行交互的编程语言,而SELECT 语句则是其中最基础也最常用的查询方式。 本文将通过对《三国志》游戏的角色数据进行分析…...

golang工程——protobuf使用及原理

相关文档 源码&#xff1a;https://github.com/grpc/grpc-go 官方文档&#xff1a;https://www.grpc.io/docs/what-is-grpc/introduction/ protobuf编译器源码&#xff1a;https://github.com/protocolbuffers/protobuf proto3文档&#xff1a;https://protobuf.dev/programmin…...

CocosCreator3.8研究笔记(二十三)CocosCreator 动画系统-动画编辑器相关功能面板说明

国庆假期&#xff0c;闲着没事&#xff0c;在家研究技术~ 上一篇&#xff0c;我们介绍了动画剪辑、动画组件以及基本的使用流程&#xff0c;感兴趣的朋友可以前往阅读&#xff1a; CocosCreator 动画系统-动画剪辑和动画组件介绍。 今天&#xff0c;主要介绍动画编辑器相关功能…...

免费 AI 代码生成器 Amazon CodeWhisperer 初体验

文章作者&#xff1a;浪里行舟 简介 随着 ChatGPT 的到来&#xff0c;不由让很多程序员感到恐慌。虽然我们阻止不了 AI 时代到来&#xff0c;但是我们可以跟随 AI 的脚步&#xff0c;近期我发现了一个神仙 AI 代码生产工具 CodeWhisperer &#xff0c;它是一项基于机器学习的服…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...