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

数据结构-- 并查集

0. 引入

并查集是来解决等价问题的数据结构。

离散数学中的二元关系。

等价关系需满足自反性、对称性、传递性。
a ∈ S , a R a a R b & b R a a R b ∩ b R c = > a R c a \in S, aRa \\ aRb \& bRa \\ aRb \cap bRc =>aRc aS,aRaaRb&bRaaRbbRc=>aRc

1. 需要实现的操作

给定n个数据,看能划分多少个等价类。

初始时即分为n个等价类,然后再一一合并。

所以需要实现的操作为:

  1. 合并两个等价类
  2. 查找元素属于哪个等价类

2. 实现

2.0 父节点
vector<int> pa;
2.1 查找
int Find(int k)
{return k == pa[k] ? k : Find(pa[k]);
}
2.2 合并
void Union(int a0, int a1)
{int p0 = Find(a0);int p1 = Find(a1);if ( p0 != p1 ) {pa[p0] = p1;}
}
2.3 路径压缩

对于查找来说如果简单的递归的话,最坏的情况便是全都在左子树。

(0,1) (0,2) (0,3) (0, 4) ... (0, n)

出现失去平衡
这样会导致单次查询如同一个链表一样达到O(n)

只需要改动一点点就可以完成路径压缩。

int Find(int k)
{
return k == pa[k] ? k : pa[k] = Find(pa[k]);
}
2.4 按节点数合并

可以令开一个数组,记录当前节点下的节点数。在合并的时候取小的节点合并到大的节点上去。

void Union(int a1, int a2)
{int p1 = Find(a1);int p2 = Find(a2);if ( p1 == p2)return;if (sz[p1] < sz[p2]) {pa[p1] = p2;sz[p2] += sz[p1];}else {pa[p2] = p1;sz[p1] += sz[p2];}     
}

3. 类封装

3.1 路径压缩
class UnionFind {public:explicit UnionFind(int sz):cnt(sz),pa(sz){iota(pa.begin(), pa.end(), 0);}int Find(int k ){return k == pa[k] ? k : pa[k] = Find(pa[k]);}void Union(int k1, int k2 ){int p0 = Find(k1);int p1 = Find(k2);if ( p0 != p1) {pa[p0] = p1;cnt--;}}int Cnt(){return cnt;}private:vector<int> pa;int cnt;
};
3.2 按节点数合并
public:
class UnionFind {public:explicit UnionFind(int _sz):cnt(_sz),pa(_sz),sz(_sz, 1){iota(pa.begin(), pa.end(), 0);}int Find(int k ){return k == pa[k] ? k : Find(pa[k]);}void Union(int k1, int k2 ){int p0 = Find(k1);int p1 = Find(k2);if (p0 == p1)return ;if (sz[p0] < sz[p1] ) {pa[p0] = p1;sz[p1] += sz[p0];}else {pa[p1] = p0;sz[p0] += sz[p1];}}int Cnt(){return cnt;}int Size(int idx){ return sz[idx]; }private:vector<int> pa,sz;int cnt;
};
4. 参考

lFoll题解
OIWIKI

相关文章:

数据结构-- 并查集

0. 引入 并查集是来解决等价问题的数据结构。 离散数学中的二元关系。 等价关系需满足自反性、对称性、传递性。 a ∈ S , a R a a R b & b R a a R b ∩ b R c > a R c a \in S, aRa \\ aRb \& bRa \\ aRb \cap bRc >aRc a∈S,aRaaRb&bRaaRb∩bRc>a…...

优维产品最佳实践第12期:IT资源管理首页丰富

​ 背 景 当我们进入平台后&#xff0c;默认跳转至IT资源管理首页&#xff0c;因此该页面的优化与丰富将极大的提高平台使用者的体验和效率。优化后的首页可以更好地展示常用模型、小产品、外部系统、以及保存的所有关系查询和快速查询条件&#xff0c;使用户能够更快捷、方便…...

【Nginx34】Nginx学习:安全链接、范围分片以及请求分流模块

Nginx学习&#xff1a;安全链接、范围分片以及请求分流模块 又迎来新的模块了&#xff0c;今天的内容不多&#xff0c;但我们都进行了详细的测试&#xff0c;所以可能看起来会多一点哦。这三个模块之前也从来都没用过&#xff0c;但是通过学习之后发现&#xff0c;貌似还都挺有…...

PO模式在selenium自动化测试框架的优势

大家都知道po模式可以提高代码的可读性和减少了代码的重复&#xff0c;但是相对的缺点还有&#xff0c;今天通过本文一起学习下PO模式在selenium自动化测试框架的优势&#xff0c;需要的朋友可以参考下 PO模式简介 1.什么是PO模式 PO模型是:Page Object Model的简写 页面对象…...

Java操作Elasticsearch(新增数据)

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…...

Android中级——MVVM

MVVM MVVM是什么&#xff1f;MVVM实现前提ModelViewModelView MVVM是什么&#xff1f; Model-View-ViewMode架构&#xff0c;可看作MVP改进版&#xff0c;将此前Presenter的逻辑操作交给ViewMode中的Binder去处理 Mode&#xff1a;封装数据存储及相关操作逻辑&#xff0c;与MV…...

AIGC:引领人工智能和游戏产业融合的里程碑

目录 引言&#xff1a; 一、AIGC简介 二、AIGC的意义和作用 三、AIGC的未来展望 四、AIGC的影响和成果 五、结论 引言&#xff1a; 人工智能技术的快速发展在过去几年中引起了全球范围内的广泛关注和热议。其中&#xff0c;AIGC&#xff08;Artificial Intelligence and G…...

ubuntu安装rust教程

参考【Rust】Linux上安装Rust开发环境 sudo apt-get install curl# 注意&#xff0c;不开代理很可能下不到&#xff0c;一直报403 export RUSTUP_DIST_SERVERhttps://mirrors.ustc.edu.cn/rust-static export RUSTUP_UPDATE_ROOThttps://mirrors.ustc.edu.cn/rust-static/rustu…...

iOS UIWebView与WKWebView 那些事

一、前言介绍 UIWebView 是 iOS 2 中推出的网页容器,UIWebView是最占内存的控件;直到 iOS 8 以后,苹果推出了 WebKit 框架,其中 WKWebView 正式被推出来接替 UIWebView 的位置;iOS 12 中,苹果正式弃用 UIWebView,要求开发者用 WKWebView 全面替换 UIWebView,apple 官方…...

wps/word 之 word中的两个表格 如何合并成为一个表格(已解决)

第一步&#xff1a;新建两个表格&#xff1a; 如何实现上面的两个表格合并呢&#xff1f; 分别选定每个表格&#xff0c;然后鼠标右键---》表格属性 在表格属性中的 表格---》选择 无文字环绕。 第二个表格按照同样的方法 设置 无文字环绕。 然后将中的文本行删去即可以了。选…...

02HTML功能元素

1.功能元素 1.1.列表标签 ​ 列表标签的作用: 给一堆数据添加列表语义, 也就是告诉搜索引擎告诉浏览器这一堆数据是一个整体 - HTML中列表标签的分类 ​ 无序列表(最多)(unordered list) ​ 有序列表(最少)(ordered list) ​ 定义列表(其次)(definition list) 1.1.1.无序列…...

并发编程-延时队列DelayQueue

数据结构学习网站&#xff1a; Data Structure Visualization 思维导图 DelayQueue &#xff08;延时队列&#xff09; DelayQueue 是一个支持延时获取元素的阻塞队列 &#xff0c; 内部采用优先队列 PriorityQueue 存储元素&#xff0c;同时元素必须实现 Delayed 接口&#x…...

Python之哈希表-遍历和有序性

Python之哈希表-遍历和有序性 有序性 字典元素是按照key的hash值无序存储的。 但是&#xff0c;有时候我们却需要一个有序的元素顺序&#xff0c;Python 3.6之前&#xff0c;使用OrderedDict类可以做到&#xff0c;3.6开 始dict自身支持。 d1 {b:33, c:True, d:[1], f:234…...

Oracle数据库完整卸载的完整步骤

时间&#xff1a;2023-03-15来源&#xff1a;系统城装机大师作者&#xff1a;佚名 1、停止所有Oracle服务 进入计算机管理&#xff0c;在服务中&#xff0c;找到oracle开头的所有服务&#xff0c;右击选择停止。 快捷键&#xff1a;ctrlshiftesc打开任务管理器 文章来源 Or…...

HP OfficeJet Pro 8020 如何更换碳粉盒

环境&#xff1a; HP OfficeJet Pro 8020 问题描述&#xff1a; HP OfficeJet Pro 8020 如何更换碳粉盒 解决方案&#xff1a; 更换碳粉盒 更换所有墨水不足的碳粉盒或空碳粉盒。 1.打开前挡盖&#xff0c;然后提起碳粉盒检修门。 打开打印机门 2.等待笔架停止后再继续操作…...

【Javascript】基础数据类型

目录 基础数据类型 1.number 字面量声明 数字对象方式声明 整数判断 指定返回小数位数 NaN-表示非数字值 浮点精度 解决误差 String 字面量声明 数字对象声明 连接运算符 获取长度 大小写转换 转换成大写 转换成小写 ​编辑 移除空白 获取单字符 ​编辑 截…...

【C语言】进阶——程序编译

目录 一&#xff1a;&#x1f512;程序环境 程序的翻译环境和执行环境 &#x1f4a1;1.1翻译环境 预编译阶段&#xff1a; 编译阶段&#xff1a; 汇编阶段&#xff1a; 链接阶段&#xff1a; &#x1f4a1;1.2运行环境 二&#xff1a;&#x1f512;预处理详解 &…...

记录阿里云服务器(Centos7.9)部署Thingsboard(3.4.2)遇到的一些问题

记录编译Thingsboard遇到的一些问题 部署了一个thingsboard项目到阿里云服务器上&#xff0c;历时十一天&#xff0c;遇到了很多困难&#xff0c;国内关于Thingsboard的资料确实很少&#xff0c;所以想着写一篇博客记录一下&#xff0c;或许能够给以后编译遇到类似问题的人一些…...

docker更新容器映射端口

一个容器已经暴露了一个端口被外界使用&#xff0c;但是这个端口被公司不允许使用&#xff0c;需要修改为其他的端口&#xff0c;怎么办&#xff1f; 1、删除原容器&#xff0c;重启新容器 删除已启动容器&#xff0c;从镜像重启新容器。2、修改原容器配置文件 3、生成镜像&…...

Pr快捷键

Pr快捷键 以下快捷键都是在英文输入法下 一、隐藏顶部项目信息 Ctrl\ 注意&#xff1a;是反斜杠&#xff0c;回车上面的按键二、单独放大窗口 选中面板按~键三、放大/缩小时间轴素材 \四、自动选中素材 序列菜单-选择跟随播放指示器五、快速定位间隙 SHIFT鼠标拖动素材 …...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...