数据结构:并查集讲解

并查集

    • 1.并查集原理
    • 2.并查集实现
    • 3.并查集应用
    • 4.并查集的路径压缩

1.并查集原理

在一些应用问题中,需要将n个不同的元素划分成一些不相交的集合。开始时,每个元素自成一个单元素集合,然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-findset)。
在这里插入图片描述

如何合并两个集合

  1. 先找到两个集合的根部(负数为根部)。
  2. 以合并AB为例子,假设让B合并到A,A减去B的值,即变成-2;然后让B的值变成A的下标0
    在这里插入图片描述

观察合并过程,可以得出以下结论:

  1. 数组的下标对应集合中元素的编号
  2. 数组中如果为负数,负号代表根,数字代表该集合中元素个数
  3. 数组中如果为非负数,代表该元素双亲在数组中的下标



2.并查集实现

并查集一般可以解决以下问题:

  1. 查找元素属于哪个集合
    沿着数组表示树形关系以上一直找到根(即:树中中元素为负数的位置)
int FindRoot(int x)  //找根的下标位置
{int par = x;while (_ufs[par] >= 0)  //如果当前大于0,说明未到根部,更新到父亲下标{par = _ufs[par];}return par;
}

在这里插入图片描述

  1. 查看两个元素是否属于同一个集合
    沿着数组表示的树形关系往上一直找到树的根,如果根相同表明在同一个集合,否则不在
bool InSet(int x1, int x2)
{if (FindRoot(x1) == FindRoot(x2)){return true;}return false;
}
  1. 将两个集合归并成一个集合
    前面讲过,不赘述。
void Union(int x1, int x2) //联合这两棵树,默认x2并到x1
{int root1 = FindRoot(x1);int root2 = FindRoot(x2);if (abs(_ufs[root1]) < abs(_ufs[root2]))  //让小的一方并到大的一方就这样swap(root1, root2);if (root1 != root2)  //本来不是同一个树(集合){_ufs[root1] += _ufs[root2];_ufs[root2] = root1;}
}
  1. 集合的个数
    遍历数组,数组中元素为负数的个数即为集合的个数
int SetSize()const //返回树的个数
{int size = 0;for (auto e : _ufs)if (e < 0)  size++;return size;
}

完整实现:

class UnionFindSet {
public:UnionFindSet(size_t size)  //一开始全都设置为-1:_ufs(size, -1){}void Union(int x1, int x2) //联合这两棵树,默认x2并到x1{int root1 = FindRoot(x1);int root2 = FindRoot(x2);if (abs(_ufs[root1]) < abs(_ufs[root2]))  //让小的一方并到大的一方就这样swap(root1, root2);if (root1 != root2)  //本来不是同一个树(集合){_ufs[root1] += _ufs[root2];_ufs[root2] = root1;}}int FindRoot(int x)  //找根的下标位置{int par = x;while (_ufs[par] >= 0){par = _ufs[par];}return par;}bool InSet(int x1, int x2){if (FindRoot(x1) == FindRoot(x2)){return true;}return false;}int SetSize()const //返回树的个数{int size = 0;for (auto e : _ufs)if (e < 0)  size++;return size;}
private:vector<int> _ufs;
};



3.并查集应用

省份数量

在这里插入图片描述

//讲解:并查集,一个城市就是一个集合
//(1)初始每个城市自成一省
//(2)如果isConnected[i][j]为1,说明i城市和j城市在一个省,合并
//(3)合并完成后遍历数组,负数有几个集合(省份)就有几个
//实际并不一定要实现完整的功能,一般需要的功能是找根部函数class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {vector<int> ufs(isConnected.size(), -1);auto FindRoot = [&ufs](int x){   //找根函数while(ufs[x] >= 0)  //没到根{x = ufs[x];}return x;};for(int i = 0; i < isConnected.size(); i++)for(int j = 0; j < isConnected[i].size(); j++)if(isConnected[i][j] == 1)  //有关系{int root1 = FindRoot(i), root2 = FindRoot(j);if(root1 != root2)  //不是同个集合{ufs[root1] += ufs[root2];  //这一步本题没必要其实ufs[root2] = root1;}}int ret = 0;for(auto e : ufs)  if(e < 0)  ret++;return ret;}
};

等式方程的可满足性

在这里插入图片描述

//思路:并查集,先遍历一次,建立起集合联系,如果a!=b,但a与b在一个集合中,就是相悖的,返回false
// 本题只有小写字母,可用0对应a,1对应b,依次类推
class Solution {
public:bool equationsPossible(const vector<string>& equations) {vector<int> ufs(26, -1);auto FindRoot = [&ufs](int x) {while (ufs[x] >= 0){x = ufs[x];}return x;};//先遍历一次,建立并查集for (auto str : equations)if (str[1] == '='){int root1 = FindRoot(str[0] - 'a'), root2 = FindRoot(str[3] - 'a');if (root1 != root2){ufs[root1] += ufs[root2];  //这一步没必要ufs[root2] = root1;}}//再遍历一次,如果在一个集合中就返回false;for (auto str : equations)if (str[1] == '!'){int root1 = FindRoot(str[0] - 'a'), root2 = FindRoot(str[3] - 'a');if (root1 == root2){return false;}}return true;}
};



4.并查集的路径压缩

并查集一般无需压缩路径,但对数据量大的情况想加快效率就需要压缩路径

原理:

  1. 可在查询时压缩,比如6->5->4->3(根部),先找到根部3。
  2. 把6记录下来,一路向上直到根,即让6、5、4直接做3的孩子,从而完成压缩。
int FindRoot(int x)  //找根的下标位置
{int root = x;while (_ufs[root] >= 0){root = _ufs[root];}//压缩路径while (_ufs[x] >= 0){int par = _ufs[x];  //先记录父亲下标_ufs[x] = root;x = par;}return root;
}

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

寒假作业2024.2.11

请使用递归实现n! #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <unistd.h> int fun(int n) {if (n0) {return 1;} else {return n*fun(n-1);} } int main(int argc, const char *argv[]) {int n…

Vue核心基础3:计算属性和监视属性

1 计算属性 这边以姓名案例&#xff0c;来介绍计算属性 <body><div id"root"><!-- 姓&#xff1a;<input type"text" v-model:value"firstName"><br>名&#xff1a;<input type"text" v-model:value&…

《CSS 简易速速上手小册》第10章:未来的 CSS(2024 最新版)

文章目录 10.1 CSS 的新特性和趋势10.1.1 基础知识10.1.2 重点案例&#xff1a;使用 CSS Grid 创建响应式图库10.1.3 拓展案例 1&#xff1a;利用 CSS 变量实现主题切换10.1.4 拓展案例 2&#xff1a;使用 lab() 颜色和 layer 规则优化样式 10.2 CSS Houdini&#xff1a;魔法般…

C++进阶(十四)智能指针

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、为什么需要智能指针&#xff1f;二、内存泄漏1、 什么是内存泄漏&#xff0c;内存泄漏的危…

STM32 7-8

目录 ADC AD单通道 AD多通道 DMA DMA转运数据 DMAAD多通道 ADC AD单通道 AD.c #include "stm32f10x.h" // Device header/*** brief 初始化AD所需要的所有设备* param 无* retval 无*/ void AD_Init(void) {RCC_APB2PeriphClockCmd(RCC_AP…

在程序中使用日志功能

在应用中&#xff0c;需要记录程序运行过程中的一些关键信息以及异常输出等。这些信息用来排查程序故障或者其他用途。 日志模块可以自己实现或者是借用第三方库&#xff0c;之前写过一个类似的使用Qt的打印重定向将打印输出到文件&#xff1a;Qt将打印信息输出到文件_qt log输…

【JavaEE】_HTML常用标签

目录 1.HTML结构 2. HTML常用标签 2.1 注释标签 2.2 标题标签&#xff1a;h1~h6 2.3 段落标签&#xff1a;p 2.4 换行标签&#xff1a;br 2.5 格式化标签 2.6 图片标签&#xff1a;img 2.7 超链接标签&#xff1a;a 2.8 表格标签 2.9 列表标签 2.10 表单标签 2.10…

C++继承(二):菱形继承、virtual菱形虚拟继承

目录 一、了解菱形继承 二、菱形继承的问题 三、虚拟继承virtual 3.1virtual 3.2虚拟继承解决数据冗余和二义性的原理 四、总结/继承和组合 一、了解菱形继承 单继承&#xff1a;一个子类只有一个直接父类时称这个继承关系为单继承 多继承&#xff1a;一个子类有两个或…

C++重新入门-C++ 函数

函数是一组一起执行一个任务的语句。每个 C 程序都至少有一个函数&#xff0c;即主函数 main() &#xff0c;所有简单的程序都可以定义其他额外的函数。 您可以把代码划分到不同的函数中。如何划分代码到不同的函数中是由您来决定的&#xff0c;但在逻辑上&#xff0c;划分通常…

春节折腾了4天,终于用上了win11和matlab2023b

这个春节折腾了4天&#xff0c;终于与时俱进用上了win11和matlab2023b。 新购的硬盘&#xff0c;顺丰快递给力2天半到手。 先折腾硬盘&#xff0c;连线&#xff0c;没有盘符&#xff0c;使用管理&#xff0c;初始化&#xff0c;格式化&#xff0c;新建卷。下载win11&#xff0…

导数的定义【高数笔记】

【含义】可以抽象成&#xff0c;在一个极其短的时间段内&#xff0c;温度差 / 时间差 【本质】瞬间的平均值 【分类】可以分成几类&#xff1f;每类需要注意的点 【导数存在的必要条件】 【导数与极限的关系】可以参考导数的定义的式子 【题型解法】分几个题型&#xff1f;每个…

2.12作业

程序代码&#xff1a; #include<stdlib.h> #include<string.h> #include<stdio.h>//递归实现n! int n(int element) {if(0element)return 1;return element*n(element-1); }//递归实现0-n的和 int sub_sum(int element) {if(0element)return 0;return eleme…

system V——进程间通信

上一篇博客中我介绍了system V进程间通信中的内存共享&#xff0c;但是其中还有两 种通信方式&#xff1a;消息队列、和信号量&#xff0c;接下来我将简单介绍一下&#xff0c;消息队列和 信号量以及操作系统是如何看待system V进程间通信的。1. 消息队列 a. 大致介绍 消息队…

用HTML5 + JavaScript绘制花、树

用HTML5 JavaScript绘制花、树 <canvas>是一个可以使用脚本 (通常为JavaScript) 来绘制图形的 HTML 元素。 <canvas> 标签/元素只是图形容器&#xff0c;必须使用脚本来绘制图形。 HTML5 canvas 图形标签基础https://blog.csdn.net/cnds123/article/details/112…

腾讯云4核8G服务器性能如何?支持多少用户访问?

腾讯云4核8G服务器支持多少人在线访问&#xff1f;支持25人同时访问。实际上程序效率不同支持人数在线人数不同&#xff0c;公网带宽也是影响4核8G服务器并发数的一大因素&#xff0c;假设公网带宽太小&#xff0c;流量直接卡在入口&#xff0c;4核8G配置的CPU内存也会造成计算…

{}初始化和初始化列表

C98标准中允许使用花括号对数组和自定义类型的变量进行初始化&#xff0c;C11扩展了大括号的用途&#xff0c;允许使用花括号对所有的内置类型和自定义类型进行初始化&#xff0c;使用时&#xff0c;可以加号&#xff0c;也可以不加。 对于自定义类型&#xff0c;当花括号中的常…

windows 下安装gin

go install 执行命令&#xff0c;执行不了的参考一下 https://blog.csdn.net/weixin_42592326/article/details/135946806 Golang 中没法下载第三方包解决办法-CSDN博客 go install github.com/gin-gonic/ginlatest 还是安装不了的话&#xff0c;用手机开热点&#xff0c;电…

Avaddon勒索病毒解密工具

前言 Avaddon勒索病毒被笔者称为2020年全球十大流行勒索病毒之一&#xff0c;其首次出现于2020年6月在俄罗斯某地下黑客论坛开始出售&#xff0c;该勒索病毒使用C语言进行编写&#xff0c;采用RSA-2048和AES-256加密算法对文件进行加密&#xff0c;该勒索病毒的传播方式多种多…

自动化AD域枚举和漏洞检测脚本

linWinPwn 是一个 bash 脚本&#xff0c;可自动执行许多 Active Directory 枚举和漏洞检查。该脚本基于很多现有工具实现其功能&#xff0c;其中包括&#xff1a;impacket、bloodhound、netexec、enum4linux-ng、ldapdomaindump、lsassy、smbmap、kerbrute、adidnsdump、certip…

第75讲Avatar头像FooterHome实现

Avatar头像实现 avatar&#xff1a; <template><el-dropdown><span class"el-dropdown-link"><el-avatar shape"square" :size"40" :src"squareUrl" /></span><template #dropdown><el-drop…