数据结构--并查集
一、并查集的概念
并查集是一种树型的数据结构,用于处理一些不相交集合(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 ,它是一项基于机器学习的服…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
QT开发技术【ffmpeg + QAudioOutput】音乐播放器
一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下,音视频内容犹如璀璨繁星,点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频,到在线课堂中知识渊博的专家授课,再到影视平台上扣人心弦的高清大片,音…...
