【算法与数据结构】并查集详解
目录
一,什么是并查集
二,并查集的结构
三,并查集的代码实现
1,并查集的大致结构和初始化
2,find操作
3,Union操作
4,优化
小结:
四,并查集的应用场景
省份数量[OJ题]
一,什么是并查集
核心概念:并查集是一种 用于管理元素分组 的数据结构。
在一些应用问题中,需将n个不同的元素划分成一些不相交的集合,开始时,n个元素各自成一个集合,然后按照一定规律将部分集合合成一个集合,也就是集合合并。并查集(union-find)适合来描述这类问题。
对于并查集,我们可以将它看成是一个森林,森林是由多棵树组成的,并查集中的一个个集合就可以看作是树。
示例:

二,并查集的结构
并查集的存储结构和树的双亲表示法相似。
所谓双亲表示法,就是在树的节点中,只存储父节点的指针,不存储孩子节点的指针。通过指针可以找到父节点。因为对于一颗树来说,可能有多个孩子 ,但只有一个父节点。

对于上图中:
节点0的数组值为-4,说明该节点为根节点。
节点6的数组值为0,说明该节点的父节点为0。
节点7的数组值为0,说明该节点的父节点为0。
节点8的数组值为0,说明该节点的父节点为0。
三,并查集的代码实现
并查集主要支持一下操作:
- 查询(find),查询一个元素在哪个集合中。
- 合并(union),将两个集合合并为一个。
1,并查集的大致结构和初始化
class UnionFind
{
public:
UnionFind(size_t n)
:_ufs(n,-1)
{}//......
private:
vector<int> _ufs;
};
2,find操作
在并查集中找到包含x的根
int findRoot(int x)
{
int root = x;while (_ufs[root] >= 0)
root = _ufs[root];return root;
}
3,Union操作
合并两个集合
void Union(int x1, int x2)
{
int root1 = findRoot(x1);
int root2 = findRoot(x2);
if (root1 == root2)
return; //在同一个集合中//这里在合并的时候采用数据量小的向数据量大的合并
//也就是小树向大树合并
if (abs(_ufs[root1]) < abs(_ufs[root2]))//root1节点更少
{
_ufs[root2] += _ufs[root1];
_ufs[root1] = root2; //小树合并到大树
}
else
{
//root2节点更少
_ufs[root1] += _ufs[root2];
_ufs[root2] = root1;
}
}
4,优化
当树比较高时,我们在反复查某个节点的根节点时,每次都会花费大量时间。
优化方法:路径压缩,只要查找某个节点一次,就将查找路径上的所有节点挂到根节点下面。
如图:查找D的根A,查找路径上包含节点B,将节点D和节点B直接挂在根节点A的下面。

//路径压缩
int findRoot(int x)
{int root = x;while (_ufs[root] >= 0)root = _ufs[root];//路径压缩while (_ufs[x] >= 0){int parent = _ufs[x];_ufs[x] = root; //挂在根节点的下面x = parent;}return root;
}
小结:
上述实现的并查集,支持连续元素。如果是处理非连续元素,需要使用哈希表代替数组(需额处理元素与索引的映射)。
核心思路:
- 哈希映射:用
unordered_map将任意类型元素映射为连续整数ID,内部用数组管理父节点动态扩容:自动添加新元素,无需预先指定规模。
模板化:支持泛型数据类型(如
string等)。
四,并查集的应用场景
连通性检测:判断网络中两个节点是否连通。
最小生成树(Kruskal算法):动态合并边,避免环。
社交网络分组:快速合并好友关系,查询是否属于同一社交圈。
总结:
并查集通过高效的查找与合并操作,成为处理动态连通性问题的核心数据结构。其优化方法(路径压缩、按秩合并)确保了接近常数的单次操作时间复杂度,适用于大规模数据场景。
其中的按秩合并就是合并集合时小树向大树合并。
省份数量[OJ题]
题目链接:LCR 116. 省份数量 - 力扣(LeetCode)

isConnected[i][j]=1,表示城市i和j连通,连通的城市为一个省份。用并查集将连通的数据放入一个集合,再统计最后的集合个数即可。
class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {int n=isConnected.size();vector<int> _ufs(n,-1);//查找根auto find=[&](int x)->int{int root=x;while(_ufs[root]>=0)root=_ufs[root];return root;};for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(isConnected[i][j]==1){//合并i和j集合int rooti=find(i),rootj=find(j);if(rooti!=rootj){_ufs[rooti]+=_ufs[rootj];_ufs[rootj]=rooti;}}}//统计集合数int ret=0;for(auto x:_ufs){if(x<0)ret++;}return ret;}
};
相关文章:
【算法与数据结构】并查集详解
目录 一,什么是并查集 二,并查集的结构 三,并查集的代码实现 1,并查集的大致结构和初始化 2,find操作 3,Union操作 4,优化 小结: 四,并查集的应用场景 省份…...
deepseek多列数据对比,联想到excel的高级筛选功能
目录 1 业务背景 2 deepseek提示词输入 3 联想分析 4 EXCEL高级搜索 1 业务背景 系统上线的时候经常会遇到一个问题,系统导入的数据和线下的EXCEL数据是否一致,如果不一致,如何快速找到差异值,原来脑海第一反应就是使用公…...
Windows操作系统部署Tomcat详细讲解
Tomcat是一个开源的Java Servlet容器,用于处理Java Web应用程序的请求和响应。以下是关于Tomcat的用法大全: 一、安装Tomcat 下载 访问Apache Tomcat官方网站(https://tomcat.apache.org/),根据你的操作系统…...
每日Attention学习23——KAN-Block
模块出处 [SPL 25] [link] [code] KAN See In the Dark 模块名称 Kolmogorov-Arnold Network Block (KAN-Block) 模块作用 用于vision的KAN结构 模块结构 模块代码 import torch import torch.nn as nn import torch.nn.functional as F import mathclass Swish(nn.Module)…...
今日写题04work
题目:移除链表元素 两种实现思路 思路一 使用双指针,prev,cur快慢指针解决。当cur不等于val,两个指针跳过。当等于val时,要考虑两种情况,一种是pos删,一种是头删除。 pos删除就是正常情况&am…...
Managed Lustre 和 WEKA:高性能文件系统的对比与应用
Managed Lustre 和 WEKA:高性能文件系统的对比与应用 1. 什么是 Managed Lustre?主要特点:适用场景: 2. 什么是 WEKA?主要特点:适用场景: 3. Managed Lustre 和 WEKA 的对比4. 如何选择 Managed…...
LeetCode541 反转字符串2
一、题目描述 给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。具体规则如下: 如果剩余字符少于 k 个,则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等…...
MAC 系统关闭屏幕/睡眠 后被唤醒 Wake Requests
问题;查看wake 日志 pmset -g log | grep "Wake Requests" 为 Wake Requests [*processdasd requestSleepService...info"com.apple.alarm.user-invisible-com.apple.calaccessd...电源设置命令参考: pmset -g sched //查看定时…...
论文笔记:Multi-Head Mixture-of-Experts
2024 neurips 1 背景 稀疏混合专家(SMoE)可在不显著增加训练和推理成本的前提下提升模型的能力【比如Mixtral 8*7B,表现可以媲美LLaMA-2 70B】 但它也有两个问题 专家激活率低(下图左) 在优化时只有一小部分专家会被…...
vue和Django快速创建项目
一、VUE 1.创建 Vue 3 JavaScript 项目 npm create vitelatest 项目名称 -- --template vue创建 Vue 3 TypeScript 项目 npm create vitelatest 项目名称 -- --template vue-ts 2.然后 cd 项目名称 npm install npm install axios # 发送 API 请求 npm install pinia …...
Java LinkedList(单列集合)
LinkedList 是 Java 中实现了 List 接口的一个类,它属于 java.util 包。与 ArrayList 不同,LinkedList 是基于双向链表实现的,适合于频繁进行插入和删除操作的场景。 1. LinkedList 的基本特性 基于链表实现:LinkedList 使用双向…...
多线程基础面试题剖析
一、线程的创建方式有几种 创建线程的方式有两种,一种是继承Thread,一种是实现Runable 在这里推荐使用实现Runable接口,因为java是单继承的,一个类继承了Thread将无法继承其他的类,而java可以实现多个接口࿰…...
.NET SixLabors.ImageSharp v1.0 图像实用程序控制台示例
使用 C# 控制台应用程序示例在 Windows、Linux 和 MacOS 机器上处理图像,包括创建散点图和直方图,以及根据需要旋转图像以便正确显示。 这个小型实用程序库需要将 NuGet SixLabors.ImageSharp包(版本 1.0.4)添加到.NET Core 3.1/ …...
EasyExcel提取excel文档
目录 一、前言二、提取excel文档2.1、所有sheet----获取得到headerList和总行数2.2、所有sheet----获取合并单元格信息2.3、读取某个sheet的每行数据一、前言 EasyExcel 是阿里巴巴开源的一个高性能 Excel 读写库,相比于 Apache POI 和 JXL,它有明显的优势,特别是在处理大数…...
第十五届蓝桥杯嵌入式省赛真题(满分)
第十五届蓝桥杯嵌入式省赛真题 目录 第十五届蓝桥杯嵌入式省赛真题 一、题目 二、分析 1、配置 2、变量定义 3、LCD显示模块 4、按键模块 5、数据分析和处理模块 1、频率突变 2、频率超限 3、数据处理 三、评价结果 一、题目 二、分析 1、配置 首先是配置cubemx…...
ASP.NET Core Web应用(.NET9.0)读取数据库表记录并显示到页面
1.创建ASP.NET Core Web应用 选择.NET9.0框架 安装SqlClient依赖包 2.实现数据库记录读取: 引用数据库操作类命名空间 创建查询记录结构类 查询数据并返回数据集合 3.前端遍历数据并动态生成表格显示 生成结果:...
【Sceneform-EQR】实现3D场景背景颜色的定制化(背景融合的方式、Filament材质定制)
写在前面的话 Sceneform-EQR是基于(filament)扩展的一个用于安卓端的渲染引擎。故本文内容对Sceneform-EQR与Filament都适用。 需求场景 在使用Filament加载三维场景的过程中,一个3D场景对应加载一个背景纹理。而这样的话,即便…...
LeetCode1706
LeetCode1706 目录 LeetCode1706题目描述示例题目理解问题描述 示例分析思路分析问题核心 代码段代码逐行讲解1. 获取网格的列数2. 初始化结果数组3. 遍历每个球4. 逐行模拟下落过程5. 检查是否卡住6. 记录结果7. 返回结果数组 复杂度分析时间复杂度空间复杂度 总结的知识点1. …...
2517. 礼盒的最大甜蜜度(Maximum Tastiness of Candy Box)
2517. 礼盒的最大甜蜜度(Maximum Tastiness of Candy Box) 问题描述 给定一个正整数数组 price,其中 price[i] 表示第 i 类糖果的价格,另给定一个正整数 k。商店将 k 类不同糖果组合成礼盒出售。礼盒的甜蜜度是礼盒中任意两种糖…...
Golang 的字符编码与 regexp
前言 最近在使用 Golang 的 regexp 对网络流量做正则匹配时,发现有些情况无法正确进行匹配,找到资料发现 regexp 内部以 UTF-8 编码的方式来处理正则表达式,而网络流量是字节序列,由其中的非 UTF-8 字符造成的问题。 我们这里从 G…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
