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

高阶数据结构之并查

并查集的概念

        之前我们曾学过树,二叉树、二叉搜索树、红黑树、AVL树等,而并查集可以看做是这些树的集合,也就是森林,它也是一种树型结构,不过是顺序的树型结构,如果有学过堆的同学应该会很熟悉。

        它的作用是判断集合是否相交,并且将有关系的集合进行合并,并且可以查询这些集合,这就是为什么它被称作并查集。

概念:并查集是一种树型结构,从结构上看和堆十分类似

作用:它可以用来判断集合是否相交、合并相关集合、并且提供查询操作

并查集的具体实现

        假设有个公司秋招,它招了10个人,其中有4个湖南的(0,3,5,8),3个广东的(1,4,6),3个广西的(2,7,9),最初这十个人互不相识,我们可以看做10个人互相之间没有关系,因此可以这样建表。

              

        由于十个人互相之间没有关系,可以看做每个个体自己就单纯代表自己。

        然后他们到达公司后,公司的经理以地域划分,并且分别选拔了人为队长。

        其中湖南的0号为队长,广东的1号为队长,广西的2号为队长,这样这三伙人就分别有了关系,表就变成了这样。

                       

         从表中可以看出来,我们能从队员找到队长,这可以看做是一个树型结构。

        这就是并查集的表示,而有时候,又会出现合并的情况,依旧拿上面的例子说。

        公司有个项目,需要多个组合作,经理让湖南组和广东组一起合作,来完成这个项目,然后让0号员工带队,此时湖南组和广东组应该合并,其合并过程和分组过程类似,最后的数据如下   

        可以看到,1号员工的组长变成了0,而其下面的组员没变,整体结构变成了这样:

         这就是并查集的合并。

        那么具体的代码如下:

#include<iostream>
#include<vector>
#include<map>
using namespace std;class DSU {
public:DSU(int n):_v(n,-1){}int findRoot(int x){int root = x;while (_v[root] >= 0){root = _v[root];}return root;}void Union(const int& x1, const int& x2){int root1 = findRoot(x1);int root2 = findRoot(x2);if (root1 != root2){_v[root1] += _v[root2];_v[root2] = root1;}}int GetSize(){int n = 0;for (int i = 0; i < _v.size(); i++){if (_v[i] < 0){n++;}}return n;}private:vector<int> _v;
};

路径压缩

        在并查集的使用过程中,可能会在极端情况下出现单边树的情况,或者当数据量过大,树结构有很多层的情况,这会导致并查集的查询效率降低。

        比如上面的场景,假设所有人都让上一号人进行管理,那么就会变成一个单边树,查询组长的效率就会降低。

        

        这时就需要路径压缩算法来减少层数,这样就能够提高效率。

        我们可以在每次寻找根的时候,可以顺便将路径给压缩,即直接将节点和根连接在一起。

 

	int findRoot(int x){int root = x;while (_v[root] >= 0){root = _v[root];}//此时找到了root,也有xwhile(_v[x] >= 0){int parent = _v[x];_v[x] = root;x = parent;}return root;}

总结

        并查集是一个树型结构,用于查询和合并都很方便,通过合并和查询,可以很快的查询到有关系的数据成员

相关文章:

高阶数据结构之并查

并查集的概念 之前我们曾学过树&#xff0c;二叉树、二叉搜索树、红黑树、AVL树等&#xff0c;而并查集可以看做是这些树的集合&#xff0c;也就是森林&#xff0c;它也是一种树型结构&#xff0c;不过是顺序的树型结构&#xff0c;如果有学过堆的同学应该会很熟悉。 它的作用是…...

Pandas04

Pandas01 Pandas02 Pandas03 文章目录 内容回顾1 数据的合并和变形1.1 df.append (了解)1.2 pd.concat1.3 merge 连接 类似于SQL的join1.4 join (了解) 2 变形2.1 转置2.2 透视表 3 MatPlotLib数据可视化3.1 MatPlotLib API 套路 &为什么要可视化3.2 单变量可视化3.3 双变量…...

ECMAScript 标准解析及应用

摘要&#xff1a; 本文深入解析了 ECMAScript 标准&#xff0c;包括其发展历程、核心语法、数据类型、对象模型、函数特性等方面。详细阐述了如何在实际的 Web 开发和 JavaScript 编程中应用这些特性&#xff0c;通过具体的代码示例展示了 ECMAScript 标准在构建高效、健壮的应…...

2025最新版Java面试八股文大全

一、Java并发面试题 1、 ThreadLocal 1.1 谈谈你对ThreadLocal的理解&#xff1f; ThreadLocal的作用主要是做数据隔离&#xff0c;填充的数据只属于当前线程&#xff0c;变量的数据对别的线程而言是相对隔离的。它不是针对程序的全局变量&#xff0c;只是针对当前线程的全局…...

从零开始学AI,完成AI 企业知识库的AI问答搭建

1&#xff1a;本地安装一个ollama玩下&#xff0c;ollama下载模型默认路径为C盘&#xff0c;但该盘空间不足。 解决方案&#xff1a;添加系统环境变量OLLAMA_MODELS&#xff0c;设置其值为新的路径。 2&#xff1a;安装完成后&#xff0c;访问http://127.0.0.1:11434/ 查看服务…...

路过石岩浪心古村

周末常去的七彩城堡儿童乐园附近经常有老房子&#xff0c;没想到老房子最多的地方还是浪心古村。而且越看越有历史。 见到一座写着《序西书室》的房子&#xff0c;我最开始以为是一个古代的学校。但是查了百度更加不知道什么意思了哈。‌“序西书室”‌是指《文心雕龙》中的一个…...

【Leecode】Leecode刷题之路第93天之复原IP地址

题目出处 93-复原IP地址-题目描述 题目描述 个人解法 思路&#xff1a; todo代码示例&#xff1a;&#xff08;Java&#xff09; todo复杂度分析 todo官方解法 93-复原IP地址-官方解法 方法1&#xff1a;回溯 思路&#xff1a; 代码示例&#xff1a;&#xff08;Java&…...

121. 买卖股票的最佳时机

题目链接&#xff1a;https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/?envTypestudy-plan-v2&envIdtop-100-liked 算法思路&#xff1a; 虽然已经提示我们使用贪心算法了&#xff0c;但是我最开始的时候却不知道怎么使用&#xff0c;因为如果…...

Python Polars快速入门指南:LazyFrames

前文已经介绍了Polars的Dataframe, Contexts 和 Expressions&#xff0c;本文继续介绍Polars的惰性API。惰性API是该库最强大的功能之一&#xff0c;使用惰性API可以设定一系列操作&#xff0c;而无需立即运行它们。相反&#xff0c;这些操作被保存为计算图&#xff0c;只在必要…...

OpenCV-Python实战(10)——形态学

1、腐蚀 cv2.erode() 可以删除图像中的噪音点。 可以删除毛边。 分割图像&#xff08;当图像连接的不够紧密时&#xff09; 。 img cv2.erode(src*,kernel*,anchor*,iterations*,borderType*,borderValue*)img&#xff1a;目标图像。 src&#xff1a;原始图像。 kernel&…...

在Windows上读写Linux磁盘镜像的一种方法

背景 嵌入式开发中&#xff0c;经常会把系统的Linux磁盘镜像保存到Windows上&#xff0c;以便上传到网盘备份或发送给工厂&#xff0c;但是如果想读取/修改镜像中的某个文件&#xff0c;一般有2种方案&#xff1a; 直接访问 就是用虚拟磁盘软件将镜像文件挂载成磁盘&#xf…...

基于STM32F103控制L298N驱动两相四线步进电机

文章目录 前言一、模块参数二、接口说明三、准备工作四、直流电机驱动引脚接线效果展示 五、两相四线步进电机驱动步进电机相关概念拍数驱动时序引脚接线效果展示 六、参考示例 前言 L298N 是一种常见的双 H 桥电机驱动模块&#xff0c;广泛用于驱动直流电机和步进电机。它基于…...

Blazor开发中注册功能设计研究

Blazor开发中注册功能设计是为了用户可以高效、安全地完成注册并登录系统。以高效和用户友好为目标,结合校验、注册和登录功能,为用户提供一个完整的账户管理流程,同时保障系统安全性和稳定性。注册页面应该结构清晰、布局合理,既满足基本注册功能,又通过响应式设计与视觉…...

Docker安装体验kuboard-k8s多集群管理工具

文章目录 1.kuboard是什么&#xff1f;2.docker安装命令2.1 Linux上docker环境安装命令2.2 Windows上docker环境安装命令 3.登录访问3.1首页访问地址3.2 默认账号密码3.3 登录页3.4 首页 4总结 1.kuboard是什么&#xff1f; 参看官网: https://kuboard.cn/gitHub项目地址&…...

组建基于IPV6的网络

现在很多单位使用IPV6的网络&#xff0c;地址资源紧张的状况得到了缓解&#xff0c;很多单位目前采用双栈运行&#xff0c;就是网络设备上同时跑IPV4和IPV6。 IPV6的网络与IPV4网络的配置与IPV4基本相同&#xff0c;注意地址规则与格式的不同。 长度&#xff1a;     IPv6地…...

浙江肿瘤医院病理库存储及NAS共享存储(磁盘阵列)方案-Infortrend普安科技

Infortrend金牌代理-燊通智联信息科技发展&#xff08;上海&#xff09;有限公司与院方多轮沟通&#xff0c;详细讨论性能与容量要求&#xff0c;最终决定采用GSe统一存储设备&#xff0c;与现有病理系统服务器无缝对接&#xff0c;每台设备配1.92T SSD作缓存加速原数据读写&am…...

UE5在蓝图中使用VarestX插件访问API

在Fab中安装好VarestX免费插件 这个插件可以用来远程请求http和api等&#xff0c;返回json等格式内容 插件网址 https://www.fab.com/zh-cn/listings/d283e40c-4ee5-4e73-8110-cc7253cbeaab 虚幻里开启插件 然后网上随便搜个免费api测试一下&#xff0c;这里我找了个微博热搜…...

QML学习(五) 做出第一个简单的应用程序

通过前面四篇对QML已经有了基本的了解&#xff0c;今天先尝试做出第一个单页面的桌面应用程序。 1.首先打开Qt,创建项目&#xff0c;选择“QtQuick Application - Empty” 空工程。 2.设置项目名称和项目代码存储路径 3.这里要注意选择你的编译器类型&#xff0c;以及输出的程…...

Java日志框架:log4j、log4j2、logback

文章目录 配置文件相关1. properties测试 2. XMl使用Dom4j解析XML Log4j与Log4j2日志门面 一、Log4j1.1 Logges1.2 Appenders1.3 Layouts1.4 使用1.5 配置文件详解1.5.1 配置根目录1.5.2 配置日志信息输出目的地Appender1.5.3 输出格式设置 二、Log4j22.1 XML配置文件解析2.2 使…...

tcp 的重传,流量控制,拥塞控制

tcp 的重传解决了什么问题tcp的几种重传机制分别解决什么问题?方案 1: 超时重传方案2: 快速重传选择性确认(sack)d-sack(重复接收) 滑动窗口:累计应答 流量控制解决什么问题?如何做的?问题1: 那如果第一次发送的数据都大于缓冲区的大小怎么办?问题2: 如果剩余大小为0会发生…...

【多时段】含sop的配电网重构【含分布式电源】【已更新视频讲解】

1 主要内容 之前分享了很多配电网重构的程序&#xff0c;每个程序针对场景限定性比较大&#xff0c;程序初学者修改起来难度较大&#xff0c;本次分享一个基础程序&#xff0c;针对含sop的配电网重构模型&#xff0c;含风电和光伏&#xff0c;优化了33节点网络电压合理性&…...

angular管道传多个参数

比如有个时间管道 time.pipe.ts import { Pipe, PipeTransform } from angular/core;Pipe({ name: time }) export class TimePipe implements PipeTransform {transform(value: any,type: any,isTime: boolean,): string {// 具体逻辑不写了} }使用的时候对时间字段的处理只需…...

STM32高级 以太网通讯案例1:网络搭建(register代码)

需求描述 驱动W5500芯片&#xff0c;设置好IP&#xff0c;测试网络是否连通。 思考&#xff1a; 驱动W5500芯片是通过spi协议&#xff0c;所以和spi相关的有四个引脚&#xff0c;MOSI&#xff08;主出从入&#xff09;MISO&#xff08;主入从出&#xff09;SCK&#xff08;时…...

strncpy函数和使用案例

strncpy 是 C 语言标准库函数之一&#xff0c;用于字符串操作。它的功能是将源字符串&#xff08;source&#xff09;中的字符复制到目标字符串&#xff08;destination&#xff09;中&#xff0c;但最多复制 n 个字符。如果源字符串的长度小于 n&#xff0c;则目标字符串剩余的…...

Python调用Elasticsearch更新数据库

文章目录 Elasticsearch介绍Python调用Elasticsearch更新数据库 Elasticsearch介绍 Elasticsearch是一个基于Lucene的搜索引擎&#xff0c;它提供了一个分布式、多租户能力的全文搜索引擎&#xff0c;具有HTTP web接口和无模式的JSON文档。Elasticsearch是用Java开发的&#x…...

阿里云-将旧服务器数据与配置完全迁移至新服务器

文章目录 一&#xff1a;创建镜像二&#xff1a;将创建好的镜像复制到新服务器所在的目标地域&#xff08;如果新服务器与镜像在同一地域就不用进行这一操作&#xff09;三&#xff1a;将镜像配置到新服务器上四&#xff1a;导出安全组&#xff08;如果新服务器与旧服务器使用同…...

redis cluster实验详解

华子目录 实验环境准备部署redis cluster添加节点删除节点redis cluster集群维护 实验 环境准备 再开3台主机 先把之前3台源码编译的redis删除 [rootredis-node1 ~]# cd /usr/local/redis/ [rootredis-node1 redis]# make uninstall[rootredis-node2 ~]# cd /usr/local/redi…...

网络技术-QoS策略以及如何定义 流分类,流行为,流策略

一&#xff1a;QoS策略简介 QoS策略由如下部分组成&#xff1a; 类&#xff0c;定义了对报文进行识别的规则。 流行为&#xff0c;定义了一组针对类识别后的报文所做的QoS动作。 通过将类和流行为关联起来&#xff0c;QoS策略可对符合分类规则的报文执行流行为中定义的…...

【小程序】自定义组件的data、methods、properties

目录 自定义组件 - 数据、方法和属性 1. data 数据 2. methods 方法 3. properties 属性 4. data 和 properties 的区别 5. 使用 setData 修改 properties 的值 自定义组件 - 数据、方法和属性 1. data 数据 在小程序组件中&#xff0c;用于组件模板渲染的私有数据&…...

实验五 时序逻辑电路部件实验

一、实验目的 熟悉常用的时序逻辑电路功能部件&#xff0c;掌握计数器、了解寄存器的功能。 二、实验所用器件和仪表 1、双 D触发器 74LS74 2片 2、74LS162 1片 3、74194 1片 4、LH-D4实验仪 1台 1.双…...

时序论文34|AdaWaveNet:用于时间序列分析的自适应小波网络

论文标题&#xff1a;AdaWaveNet: Adaptive Wavelet Network for Time Series Analysis 论文链接&#xff1a;https://arxiv.org/abs/2405.11124 论文代码&#xff1a;https://github.com/comp-well-org/AdaWaveNet/ 前言 这篇文章面向非平稳时间序列进行分析与建模&#x…...

Maven怎么会出现一个dependency-reduced-pom.xml的文件

问题 今天打包时突然发现&#xff0c;多出了一个名为dependency-reduced-pom.xml的文件 解决方法 由于使用了maven-shade-plugin插件导致的&#xff0c;在 <plugin> 标签下添加 <configuration><createDependencyReducedPom>false</createDependencyR…...

Vue.js组件(6):echarts组件

1 前言 本章主要对常用的echars图表展示进行基本的组件封装。使用该组件前需要在项目中引入echarts。官网&#xff1a;Apache ECharts npm install echarts --save 2 图表组件 2.1 折线图组件 组件属性&#xff1a;chartId&#xff0c;指定图表挂载div的id&#xff0c;注意不…...

在低版本 CUDA 环境下安装高 CUDA 版本的 PyTorch 及 DGL

项目中&#xff0c;代码环境需要 PyTorch 1.12.0 以上版本&#xff0c;但服务器上的 CUDA 版本仅为 10.1&#xff0c;官方支持的 PyTorch 最高版本为 1.7.0。导致无法直接使用所需的 PyTorch 版本。而且&#xff0c;DGL 也需要 0.9.1 版本&#xff0c;而 CUDA 10.1 不支持该版本…...

【SpringMVC】REST 风格

REST&#xff08;Representational State Transfer&#xff0c;表现形式状态转换&#xff09;是一种访问网络资源的格式。传统的资源描述方式通常如下&#xff1a; http://localhost/user/getById?id1http://localhost/user/saveUser 而 REST 风格的描述则更简洁&#xff1a…...

windows C#-使用对象初始值设定项初始化对象

可以使用对象初始值设定项以声明方式初始化类型对象&#xff0c;而无需显式调用类型的构造函数。 以下示例演示如何将对象初始值设定项用于命名对象。 编译器通过首先访问无参数实例构造函数&#xff0c;然后处理成员初始化来处理对象初始值设定项。 因此&#xff0c;如果无参…...

【Sentinel】流控效果与热点参数限流

目录 1.流控效果 1.1.warm up 2.2.排队等待 1.3.总结 2.热点参数限流 2.1.全局参数限流 2.2.热点参数限流 2.3.案例 1.流控效果 在流控的高级选项中&#xff0c;还有一个流控效果选项&#xff1a; 流控效果是指请求达到流控阈值时应该采取的措施&#xff0c;包括三种&…...

安装与配置

《PHP Libxml》是一个在PHP中处理XML和HTML文档的重要库。它提供了丰富的API&#xff0c;支持DOM、SimpleXML和XMLReader等多种解析方式&#xff0c;广泛应用于各种编程语言和项目中。 安装与配置 安装: 在PHP中&#xff0c;libxml扩展通常是默认启用的。如果你需要手动安装&…...

optuna和 lightgbm

文章目录 optuna使用1.导入相关包2.定义模型可选参数3.定义训练代码和评估代码4.定义目标函数5.运行程序6.可视化7.超参数的重要性8.查看相关信息9.可视化的一个完整示例10.lightgbm实验 optuna使用 1.导入相关包 import torch import torch.nn as nn import torch.nn.functi…...

SpringAI人工智能开发框架006---SpringAI多模态接口_编程测试springai多模态接口支持

可以看到springai对多模态的支持. 同样去创建一个项目 也是跟之前的项目一样,修改版本1.0.0 这里 然后修改仓库地址,为springai的地址 然后开始写代码...

ONLYOFFICE 协作空间 3.0 新功能详解

ONLYOFFICE 协作空间 3.0 新功能详解 书接上文&#xff1a; ONLYOFFICE 协作空间 3.0 发布: 新增虚拟数据房间、用户类型、OAuth 2.0 等更新 简单的介绍了一下 ONLYOFFICE 协作空间 3.0 的新功能&#xff0c;今天我们详细介绍一下这些新功能。 关于 ONLYOFFICE 协作空间 O…...

湖南引力:低代码助力实现智慧养老管理系统

“低代码开发宛如一座神奇的桥梁&#xff0c;它以简洁高效的方式连接起创意与应用&#xff0c;降低了开发门槛&#xff0c;为企业和开发者带来前所未有的便捷与可能&#xff0c;开启了快速实现软件梦想的新征程。” ——王港&#xff0c;湖南引力科技有限公司 湖南引力科技有…...

React里使用lodash工具库

安装 使用命令 npm install lodash 页面引入 常见的引入方式 引入整个lodash对象&#xff1a; import _ from lodash按名称引入特定的函数&#xff1a; import { orderBy } from "lodash"; tips: 这两种引入方式都会引入整个lodash库&#xff0c; 体积大&#x…...

机器人C++开源库The Robotics Library (RL)使用手册(二)

由于RL库采用跨平台CMake源码,可以轻松在win、ubantu等平台部署、编译,win通常用VS编译器,为了便于使用、阅读,需要将CMake编译成VS工程。 1、准备三个工具:CMake、VS、QT 为了在Windows上编译RL和依赖项,您需要安装一个编译器(例如。,Visual Studio 2017)和跨平台构…...

Excel无法插入新单元格怎么办?有解决方法吗?

在使用Excel时&#xff0c;有时会遇到无法插入新单元格的困扰。这可能是由于多种原因导致的&#xff0c;比如单元格被保护、冻结窗格、合并单元格等。本文将详细介绍3种可能的解决方案&#xff0c;帮助你顺利插入新单元格。 一、消冻结窗格 冻结窗格功能有助于在滚动工作表时保…...

2024年-全球使用Delphi统计

Delphi是一款集成开发环境&#xff08;IDE&#xff09;&#xff0c;旨在支持开发者高效地构建桌面、移动、Web 以及控制台应用程序&#xff0c;特别适合追求速度与效率的快速应用开发&#xff08;RAD&#xff09;流程。 根据 theirstack.com 网站的数据&#xff0c;我们大致描…...

行为树详解(5)——事件驱动

【分析】 如果行为树的节点很多&#xff0c;那么会存在要经过很多节点才会走到动作节点的情况。显然&#xff0c;性能上不如状态机。 每帧都需要重新遍历一系列节点才会走到动作节点&#xff0c;而实际上很多条件节点在数帧内不会有变化&#xff0c;这是造成性能问题的重要原…...

为什么深度学习和神经网络要使用 GPU?

为什么深度学习和神经网络要使用 GPU&#xff1f; 本篇文章的目标是帮助初学者了解 CUDA 是什么&#xff0c;以及它如何与 PyTorch 配合使用&#xff0c;更重要的是&#xff0c;我们为何在神经网络编程中使用 GPU。 图形处理单元 (GPU) 要了解 CUDA&#xff0c;我们需要对图…...

Kinova在开源家庭服务机器人TidyBot++研究里大展身手

在科技日新月异的今天&#xff0c;机器人技术在家庭场景中的应用逐渐成为现实&#xff0c;改变着我们的生活方式。今天&#xff0c;我们将深入探讨一篇关于家用机器人研究的论文&#xff0c;剖析其中的创新成果&#xff0c; 论文引用链接&#xff1a;http://tidybot2.github.i…...

Elasticsearch检索之三:官方推荐方案search_after检索实现(golang)

Elasticsearch8.17.0在mac上的安装 Kibana8.17.0在mac上的安装 Elasticsearch检索方案之一&#xff1a;使用fromsize实现分页 快速掌握Elasticsearch检索之二&#xff1a;滚动查询(scrool)获取全量数据(golang) 1、search_after检索 在前面的文章介绍了fromsize的普通分页…...