【数据结构与算法-高阶】并查集

【数据结构与算法-高阶】并查集

🥕个人主页:开敲🍉

🔥所属专栏:数据结构与算法🍅

🌼文章目录🌼

1. 并查集原理

2. 并查集实现

3. 并查集应用

1. 并查集原理

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

  比如:某公司今年校招全国总共招生10人,西安招 4 人,成都招 3 人,武汉招 3 人,10 个人都来自不同的学校,开始互不相识,每个学生都是独立的小团体,现在我们给这些学生编号: {0,1,2,3,4,5,6,7,8,9};给定一下数组用来存储这些学生的编号,数组中存储的值暂且先别管,后面再解释:

  毕业后,这些学生去到了这家公司,西安、成都、武汉的学生都各自组成了一个小团体前往公司:西安小分队s1 = {0,6,7,8},成都小分队s2 = {1,4,9},武汉小分队s3 = {2,3,5}。假设 0、1、2分别是三个小分队的队长。

  在一趟漫长的火车旅行之后,小分队里的人都熟络了起来,成为了一个朋友圈:

  此时这个朋友圈在数组中的形式就变成了这样(还是先别管数组中存储的值的意义,后面会解释):

  从上图就可以清晰明白:编号 6、7、8的同学属于 0号 的小队;编号4、9的同学属于 1号 的小队;编号3、5的同学属于 2号 的小队。

  此时我们仔细观察一下数组中的值加以思考就能得出以下结论:

① 数组的下标就是同学的编号

② 数组中为负数的值所对应的下标就是队长的编号,我们在这里称之为  

③ 数组中所有为非负数的值也是队长的编号,也就是非负数的值指向根

  在公司工作了一段时间后,西安小分队中的8号同学与成都小分队的1号同学关系变得越来越亲密,经过这两位同学的相互介绍,西安小分队和成都小分队最终融合成了一个圈子:

  此时数组也变换成:

  现在0号的队伍中有了7个人,2号的队伍中有2个人,总共两个朋友圈,也可以说,总共两个根。

  通过上述例子我们可以知道,并查集一般可以解决以下问题:

① 查找元素属于哪个集合:沿着该元素位置所存储的值一路跳转查找,直到遇到存储的值为负数的下标,就是集合的 根

② 查看两个元素是否属于同一个集合:依旧是跳转查找到存储的值为负数的下标,判断两个元素是否指向同一个根

③ 将两个集合归并为一个集合

④ 判断集合的个数

2. 并查集实现
//并查集
template <class T>
class Union
{
public:Union(size_t n):_a(n,-1){}//并集void UnionCom(size_t x,size_t y){//寻找x、y所在集合的根,用root1、root2接收int root1 = FindRoot(x);int root2 = FindRoot(y);if (root1 == root2) return;//如果两个元素在同一个集合,则无需合并,直接返回_a[root1] += _a[root2];//将 root2 存储的值存入 root1 中_a[root2] = root1;//将 root2 归并到 root1下}//寻根int FindRoot(size_t x){int flag = x;while (_a[flag] >= 0) flag = _a[flag];//沿着存储的值一路查找,直到找到存储的值为负数的下标return flag;}//求集合个数size_t UnionCount(){size_t count = 0;for (int i = 0; i < _a.size(); i++){if (_a[i] < 0) count++;//存储的值是负数的就是集合的根}return count;}//判断是否在同一集合中bool UnionSam(size_t x, size_t y){return (_a[x] == _a[y] && _a[x] != -1);}private:vector<int> _a;
};
3. 并查集应用

下面题目的题解在:【每日刷题】Day134-CSDN博客 中。

LCR 116. 省份数量 - 力扣(LeetCode)

class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {int ans = 0;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]){int root1 = findRoot(i);int root2 = findRoot(j);if(root1!=root2){ufs[root1]+=ufs[root2];ufs[root2] = root1;}}}}for(int i = 0;i<ufs.size();i++){if(ufs[i]<0) ans++;}return ans;}
};

990. 等式方程的可满足性 - 力扣(LeetCode)

class Solution {
public:bool equationsPossible(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');int root2 = findRoot(str[3]-'a');if(root1!=root2){ufs[root1]+=ufs[root2];ufs[root2] = root1;}}}//不相等判断是否在同一个集合,如果在则相悖for(auto str:equations){if(str[1]=='!'){int root1 = findRoot(str[0]-'a');int root2 = findRoot(str[3]-'a');if(root1==root2) return false;}}return true;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

了解HTTPS

目录 1.HTTP认识 2.HTTP请求 3.HTTP响应 4.URL 5.HTTP方法 面试题&#xff1a;POST 和 GET区别&#xff1f; 网上关于 GET 与 POST的差别 有待商议 关于请求报头 和 响应报头 6..Host &#xff1a; 7..USer-Agent&#xff08;简称UA&#xff09; 8.状态码 9.HTTPS 是…

读懂MySQL事务隔离

什么是事务 事务就是一组原子性的SQL查询&#xff0c;或者说一个独立的工作单元。事务内的语句&#xff0c;要么全部执行成功&#xff0c;要么全部执行失败。 关于事务银行系统的应用是解释事务必要性的一个经典例子。 假设一个银行的数据库有两张表&#xff1a;支票表&#x…

【Windows】开始菜单关键错误以及系统应用闪退问题记录

一 开始菜单关键错误 Windows长时间没有重启&#xff0c;重启之后开始菜单点不进去&#xff0c;报错“关键错误”。 查询网上有两种解决方案&#xff1a; 【1】更新系统版本&#xff1b; 【2】通过powershell执行一次性恢复所有应用的指令&#xff1b; 我这边采用第二种方法&am…

如何使用pymysql和psycopg2执行SQL语句

在Python中&#xff0c;pymysql和psycopg2是两个非常流行的库&#xff0c;用于与MySQL和PostgreSQL数据库进行交互。本文将详细介绍如何使用这两个库来执行SQL查询、插入、更新和删除操作。 1. 准备工作 首先&#xff0c;确保已经安装了pymysql和psycopg2库。如果尚未安装&a…

指针函数C++

指针函数概念 指针函数在C中是一种特殊类型的函数。从本质上讲&#xff0c;它是一个函数&#xff0c;不过其返回值是一个指针类型的数据。例如&#xff0c;像int* plusfunction(int a, int b);这样的函数声明&#xff0c;plusfunction就是一个指针函数&#xff0c;它接受两个i…

CentOS7.9 下安装 Docker

第一步&#xff1a; sudo yum install -y yum-utils \ > device-mapper-persistent-data \ > lvm2 第二步&#xff1a;安装 sudo wget -O /etc/yum.repos.d/docker-ce.repo https://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo sudo yum -y install…

IT监控可视化:运维团队的智慧之眼

在当今这个数字化时代&#xff0c;IT系统已成为企业运营的核心支柱。随着业务的不断扩展和IT架构的日益复杂&#xff0c;运维团队面临着前所未有的挑战。如何高效、准确地监控和管理IT资源&#xff0c;确保系统的稳定性和可用性&#xff0c;成为了运维工作的重中之重。而IT监控…

CSS3--美若天仙!?

免责声明&#xff1a;本文仅做分享~ 目录 CSS引入方式 选择器 盒子尺寸和背景色 文字控制属性 单行文字 垂直居中 字体族 font复合属性 文本对齐方式 文本修饰线 color 文字颜色 ----- 复合选择器 伪类选择器 超链接伪类 CSS特性 继承性 层叠性 优先级 Emmet …

Linux驱动---光电开关、火焰传感器、人体红外传感器

文章目录 一、电路连接二、设备树三、驱动代码 一、电路连接 人体红外 – PF12 检测到人体时会产生一个上升沿 光电开关 – PE15 有遮挡物时会产生一个上升沿 火焰传感器 – PF5 有火焰时会产生一个上升沿 二、设备树 /{ //人体红外PF12human{ compatible "zyx,huma…

数据驱动投资:AI在股票市场的应用

当ChatGPT首次亮相时&#xff0c;其卓越的语言处理能力立刻引起了许多行业的广泛关注&#xff0c;投资界也不例外。关于ChatGPT是否能应用于投资决策的问题&#xff0c;迅速成为热门讨论的焦点。 近期&#xff0c;加拿大多伦多大学和印度孟买理工学院的研究人员联合开展了一项…

[论文阅读] DVQA: Understanding Data Visualizations via Question Answering

原文链接&#xff1a;http://arxiv.org/abs/1801.08163 启发&#xff1a;没太读懂这篇论文&#xff0c;暂时能理解的就是本文提出了一个专门针对条形图问答的数据集DVQA以及一个端到端模型SANDY&#xff0c;模型有两个版本&#xff0c;Oracle和OCR。主要解决的问题是固定词表无…

C++ —— 优先级队列(priority queue)的模拟实现

目录 杂谈 vector和list的区别 1. 优先级队列的定义 2. 优先级队列的模拟实现 3. 仿函数 链接&#xff1a; priority_queue - C Reference (cplusplus.com)https://legacy.cplusplus.com/reference/queue/priority_queue/?kwpriority_queue 杂谈 vector和list的区别 在…

UPDATE 和 DELETE数据库表的多行

文章目录 说明程序测试结果 说明 程序 *&---------------------------------------------------------------------* *& Report Z_TEST_1008 *&---------------------------------------------------------------------* *& *&--------------------------…

手机怎样改网络ip地址?内容详尽实用

随着网络技术的发展&#xff0c;更改手机IP地址已成为一种常见需求。本文将详细介绍如何在不同网络环境下更改手机IP地址&#xff0c;包括移动网络和WiFi网络&#xff0c;以及同时适用于两种网络的方法&#xff0c;内容详尽实用&#xff0c;干货满满。 一、适用于移动网络&…

vue3 vue2

vue3.0是如何变快的&#xff1f; diff算法优化 vue2的虚拟dom是进行全局的对比。vue3 新增了静态标记&#xff08;patchFlag&#xff09; 在与上次虚拟节点进行比较的时候&#xff0c;只对比带有patch Flag的节点&#xff0c;并且可以通过flag的信息得知当前节点要对比的具体内…

10.9 Qt事件处理机制

键盘按键调整label移动 #include "widget.h" #include "ui_widget.h" #include <QDebug> #include <QKeyEvent>Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);}Widget::~Widget() {delete ui;…

C++——vector

目录 一、简介 二、接口 1.构造 2.空间变化 3.增删查改 三、vector与string的区别 四、模拟实现 vector.h test.cpp 一、简介 vector&#xff0c;其实就是我们C语言学过的动态顺序表&#xff0c;一个可以存储任何数据类型&#xff0c;可以动态增长的数组。C的STL将其收…

项目完整开发的流程

流程 1.设计产品 2.写需求文档 2.1需求分析&#xff0c;后端设计数据库&#xff0c;建表&#xff0c;客户沟通&#xff0c;说完签字&#xff0c;留证据&#xff0c;防止后面扯皮&#xff0c;和防止后续变需求重新写业务 3.画原型图&#xff0c;也就是草图&#xff0c;初始的…

Java报错输出的信息究竟是什么?

Java报错输出的信息究竟是什么&#xff1f; 本篇会带大家了解一下java运行时报错输出的信息内容&#xff0c;简单学习一下虚拟机内存中Java虚拟机栈的工作方式以及栈帧中所存储的信息内容 异常信息 当你的程序运行报错时&#xff0c;你是否会好奇打印出来的那一大坨红色的究竟…

上海AI Lab视频生成大模型书生.筑梦环境搭建推理测试

引子 最近视频生成大模型层出不穷&#xff0c;上海AI Lab推出新一代视频生成大模型 “书生・筑梦 2.0”(Vchitect 2.0)。根据官方介绍&#xff0c;书生・筑梦 2.0 是集文生视频、图生视频、插帧超分、训练系统一体化的视频生成大模型。OK&#xff0c;那就让我们开始吧。 一、模…