数据结构--并查集
一、并查集的概念
并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题。常常在使用中以森林来表示。
最裸并查集:
- 合并元素a和元素b 所在的集合。
- 查询元素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;
}

相关文章:
数据结构--并查集
一、并查集的概念 并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题。常常在使用中以森林来表示。 最裸并查集: 合并元素a和元素b 所在的集合。查询元素a和元素b 是否属于同一组。是否在一个…...
Leetcode 224. 基本计算器
文章目录 题目代码(10.1 首刷看解析) 题目 Leetcode 224. 基本计算器 代码(10.1 首刷看解析) class Solution { public:int calculate(string s) {stack<int> sk; // 存储正负号sk.push(1);int sign 1;int res 0;int i…...
Linux基础命令汇总
用户管理 su 切换用户:su 用户名 logname 显示当前用户的登录用户名:logname useradd 创建用户:useradd 用户名创建用户时指定用户的主组:useradd -g 组名 用户名 usermod 添加附属组:usermod -G 组…...
JAVA 获得特定格式时间
0 背景 我们有时要获取时间,年月日时分秒周几,有时要以特定的格式出现。这时就要借助 SimpleDateFormat 或者 DateTimeFormatter。有时要某个月份有多少天需要借助 Calendar。所以有必要了解一些知识。 1 SimpleDateFormat simpledateFormat 线程不安全…...
问题: 视频颜色问题,偏绿
参考 什么是杜比视界? - https://www.youtube.com/watch?vldXDQ6VlC7g 【哈士亓说】07:HDR、杜比视界究竟是个啥?为什么这个视频还不是HDR视频? - https://www.youtube.com/watch?vrgb9Xg3cJns 正文 视频应该是 杜比视界 电…...
智能文字识别技术——AI赋能古彝文保护
前言 人工智能在古彝文古籍保护方面具有巨大的潜力和意义。通过数字化、自动化和智能化的手段,可以更好地保护和传承古彝文的文化遗产,促进彝族文化的传承和发展。 文章目录 前言一、古彝文是什么?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 来实现的,在 Vue3 中响应式数据是通过 ES6 的 Proxy来实现的。reactive 参数必须是对象 (json / arr)如果给 reactive 传递了其它对象 默…...
jvs-rules(规则引擎)和jvs智能bi(自助式数据分析)9.22更新内容
规则引擎更新功能 新增: 1.新增节点匹配筛选 用于做多个条件的数据筛选,以便将符合条件的数据传递给下一个节点进行处理,通常用于实现复杂的查询逻辑。 2.复合变量节点新增判断条件选项说明 用户可以根据自己的需求,为复合变量节点添加不…...
Leetcode算法题练习(一)
目录 一、前言 二、移动零 三、复写零 四、快乐数 五、电话号码的字母组合 六、字符串相加 一、前言 大家好,我是dbln,从本篇文章开始我就会记录我在练习算法题时的思路和想法。如果有错误,还请大家指出,帮助我进步。谢谢&…...
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 编程中,注解(Annotation)是一种元数据,它提供了关于程序代码的额外信息。注解不直接影响程序的执行,但可以在运行时提供有关程序的信息,或者让编译器执行额外的检查。 本文将详细介绍 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的那些事(5-Spring STOMP支持之连接外部消息代理)中我们已经简单介绍了各种目的地类型,如下图&…...
SQL SELECT 语句基础
在数字化的世界中,数据已经成为了一种无处不在的资源。从游戏开发到商业智能,数据分析都是不可或缺的一部分。SQL(结构化查询语言)是一种用于与数据库进行交互的编程语言,而SELECT 语句则是其中最基础也最常用的查询方式。 本文将通过对《三国志》游戏的角色数据进行分析…...
golang工程——protobuf使用及原理
相关文档 源码:https://github.com/grpc/grpc-go 官方文档:https://www.grpc.io/docs/what-is-grpc/introduction/ protobuf编译器源码:https://github.com/protocolbuffers/protobuf proto3文档:https://protobuf.dev/programmin…...
CocosCreator3.8研究笔记(二十三)CocosCreator 动画系统-动画编辑器相关功能面板说明
国庆假期,闲着没事,在家研究技术~ 上一篇,我们介绍了动画剪辑、动画组件以及基本的使用流程,感兴趣的朋友可以前往阅读: CocosCreator 动画系统-动画剪辑和动画组件介绍。 今天,主要介绍动画编辑器相关功能…...
免费 AI 代码生成器 Amazon CodeWhisperer 初体验
文章作者:浪里行舟 简介 随着 ChatGPT 的到来,不由让很多程序员感到恐慌。虽然我们阻止不了 AI 时代到来,但是我们可以跟随 AI 的脚步,近期我发现了一个神仙 AI 代码生产工具 CodeWhisperer ,它是一项基于机器学习的服…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
