数据结构--并查集

一、并查集的概念

并查集是一种树型的数据结构,用于处理一些不相交集合(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;
}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/146612.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

springmvc-页面跳转表单标签其他标签tomcat控制台中文乱码问题

1. WEB-INF下页面跳转 容器启动后&#xff0c;如何默认显示web-inf目录下的系统首页。 2. ModelAttribute来注解非请求处理方法 用途&#xff1a;预加载数据&#xff0c;会在每个RequestMapping方法执行之前调用。 特点&#xff1a;无需返回视图&#xff0c;返回类型void 示例…

Spring的注解开发-非自定义Bean的配置

非自定义Bean注解开发 非自定义Bean不能象自定义Bean一样使用Component注解及其衍生注解进行管理&#xff0c;非自定义Bean要通过工厂的方式进行实例化&#xff0c;使用Bean标注即可&#xff0c;Bean的属性为beanName&#xff0c;使用Bean注解作用在方法中&#xff0c;通过定义…

Audacity 使用教程:轻松录制、编辑音频

Audacity 使用教程&#xff1a;轻松录制、编辑音频 1. 简介 Audacity 是一款免费、开源且功能强大的音频录制和编辑软件。它适用于 Windows、Mac 和 Linux 等多种操作系统&#xff0c;适合音乐制作、广播后期制作以及普通用户进行音频处理。本教程将带领大家熟悉 Audacity 的…

基于SSM的公司项目管理系统设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用JSP技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…

【IDEA】IDEA 单行注释开头添加空格

操作 打开 IDEA 的 Settings 对话框&#xff08;快捷键为CtrlAltS&#xff09;&#xff1b;在左侧面板中选择Editor -> Code Style -> Java&#xff1b;在右侧面板中选择Code Generation选项卡&#xff1b;将Line comment at first column选项设置为false使注释加在行开…

Leetcode 69.x的平方根

给你一个非负整数 x &#xff0c;计算并返回 x 的 算术平方根 。 由于返回类型是整数&#xff0c;结果只保留 整数部分 &#xff0c;小数部分将被 舍去 。 注意&#xff1a;不允许使用任何内置指数函数和算符&#xff0c;例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1&#xff1…

【算法|贪心算法系列No.2】leetcode2208. 将数组和减半的最少操作次数

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 &#x1f354;本专栏旨在提高自己算法能力的同时&#xff0c;记录一下自己的学习过程&#xff0c;希望…

【办公自动化】在Excel中按条件筛选数据并存入新的表(文末送书)

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…

分享46个Python源代码总有一个是你想要的

分享46个Python源代码总有一个是你想要的 下载链接&#xff1a;https://pan.baidu.com/s/1oZPrXHwgzcvVpB36_dA72A?pwd8888 提取码&#xff1a;8888 chat-web项目的python后端 Django WEB商城网站项目 django-实时接口获取中国各个城市、省份、国家的新型冠状肺炎 NewsSp…

蓝桥杯每日一题2023.10.2

时间显示 - 蓝桥云课 (lanqiao.cn) 题目描述 题目分析 输入为毫秒&#xff0c;故我们可以先将毫秒转化为秒&#xff0c;由于只需要输出时分&#xff0c;我们只需要将天数去除即可&#xff0c;可以在这里多训练一次天数判断 #include<bits/stdc.h> using namespace std…

电子地图 | VINS-FUSION | 小觅相机D系列

目录 一、相关介绍 二、VINS-FUSION环境安装及使用 &#xff08;一&#xff09;Ubuntu18.04安装配置 1、Ubuntu下载安装 2、设置虚拟内存&#xff08;可选&#xff09; &#xff08;二&#xff09;VINS-FUSION环境配置 1、ros安装 2、ceres-solver安装 3、vins-fusion…

微服务moleculer03

1. Moleculer 目前支持SQLite&#xff0c;MySQL&#xff0c;MariaDB&#xff0c;PostgreSQL&#xff0c;MSSQL等数据库&#xff0c;这里以mysql为例 2. package.json 增加mysql依赖 "mysql2": "^2.3.3", "sequelize": "^6.21.3", &q…

docker基础命令

目录 一、安装docker 1、查看是否已安装docker 2、如果系统中已经存在旧的Docker 3、配置Docker的yum库 4、安装成功后&#xff0c;执行命令&#xff0c;配置Docker的yum源 5、安装Docker 6、启动和校验 7、配置镜像加速器&#xff0c;阿里云镜像加速为例 7.1、在首页的…

LabVIEW开发虚拟与现实融合的数字电子技术渐进式实验系统

LabVIEW开发虚拟与现实融合的数字电子技术渐进式实验系统 数字电子技术是所有电气专业的重要学科基础&#xff0c;具有很强的理论性和实践性。其实验是提高学生分析、设计和调试数字电路能力&#xff0c;培养学生解决实际问题的工程实践能力&#xff0c;激发学生创新意识&…

38 翻转二叉树

翻转二叉树 理解题意&#xff0c;翻转即每个结点的左右子树翻转/对调题解1 递归——自下而上题解2 迭代——自上而下 给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 提示&#xff1a; 树中节点数目范围在 [0, 100] 内-100 < Node.…

开源博客项目Blog .NET Core源码学习(3:数据库操作方式)

开源博客项目Blog采用SqlSugar模块连接并操作数据库&#xff0c;本文学习并记录项目中使用SqlSugar的方式和方法。   首先&#xff0c;数据库连接信息放在了App.Hosting项目的appsettings.json中DbConfig节&#xff0c;支持在DbConfig节配置多个数据库连接信息&#xff0c;以…

探索腾讯企业邮箱替代方案:选择适合你的新邮件服务

腾讯企业邮箱作为一款广受欢迎的企业级电子邮件服务&#xff0c;已经在国内市场占据了相当大的份额。然而&#xff0c;随着全球市场竞争的加剧&#xff0c;腾讯企业邮箱也面临着海外市场的挑战。本文将探讨腾讯企业邮箱出海的劣势&#xff0c;并推荐一些替代品牌&#xff0c;以…

多线程 - 阻塞式队列

阻塞队列 阻塞队列,也是一个队列 ~~ 先进先出 实际上有一些特殊的队列,不一定非得遵守先进先出的 ~~ 优先级队列(PriorityQueue) 阻塞队列,也是特殊的队列,虽然也是先进先出的,但是带有特殊的功能: 阻塞 如果队列为空,执行出队列操作,就会阻塞.阻塞到另一个线程往队列里添加元…

软件测试之Python基础学习

目录 一、Python基础 Python简介、环境搭建及包管理 Python简介 环境搭建 包管理 Python基本语法 缩进(Python有非常严格的要求) 一行多条语句 断行 注释 变量 基本数据类型(6种) 1. 数字Number 2. 字符串String 3. 列表List 4. 元组Tuple 序列相关操作方法 …

gitlab配置webhook限制提交注释

一、打开gitlab相关配置项 vim /etc/gitlab/gitlab.rb gitlab_shell[custom_hooks_dir] "/etc/gitlab/custom_hooks" 二、创建相关文件夹 mkdir -p /etc/gitlab/custom_hooks mkdir -p /etc/gitlab/custom_hooks/post-receive.d mkdir -p /etc/gitlab/custom_h…