当前位置: 首页 > 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;
}

在这里插入图片描述

http://www.lryc.cn/news/179627.html

相关文章:

  • Leetcode 224. 基本计算器
  • Linux基础命令汇总
  • JAVA 获得特定格式时间
  • 问题: 视频颜色问题,偏绿
  • 智能文字识别技术——AI赋能古彝文保护
  • Linux压缩和解压命令大全:tar、gzip和zip完整教程
  • Vue3 reactive和ref详解
  • jvs-rules(规则引擎)和jvs智能bi(自助式数据分析)9.22更新内容
  • Leetcode算法题练习(一)
  • Xilinx FPGA 7系列 GTX/GTH Transceivers (5)-- Aurora 8b10b 信号传输实战--小试牛刀
  • 第三章:最新版零基础学习 PYTHON 教程(第七节 - Python 运算符—Python 成员身份和身份运算符)
  • 【Java 基础篇】Java 注解详解
  • MVVM框架下两窗口的消息传递
  • ROS2 从头开始​​:第6部分 - ROS2 中的 DDS,用于可靠的机器人通信
  • WebSocket的那些事(6- RabbitMQ STOMP目的地详解)
  • SQL SELECT 语句基础
  • golang工程——protobuf使用及原理
  • CocosCreator3.8研究笔记(二十三)CocosCreator 动画系统-动画编辑器相关功能面板说明
  • 免费 AI 代码生成器 Amazon CodeWhisperer 初体验
  • 谷歌扩展下载
  • Mac上如何修复损坏的音频?试试iZotope RX 10,对音频进行处理,提高音频质量!
  • Mysql各种锁
  • 【算法导论】快速排序
  • QT之QScriptEngine的用法介绍
  • vim 工具的使用
  • RPA有什么优势?RPA的8大优势!建议学习!
  • 初级篇—第二章SELECT查询语句
  • PostMan的学习
  • 配置OSPF路由
  • CCF CSP认证 历年题目自练Day17