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

并查集(蓝桥杯 C++ 题目 代码 注解)

目录

介绍:

模板:

题目一(合根植物):

代码:

题目二(蓝桥幼儿园): 

代码:

题目三(小猪存钱罐):

代码:

题目四(星球大战):

代码:​​​​​​​

介绍:

并查集(Disjoint-set Data Structure),也称为不相交集合数据结构,用于解决集合的合并与查询问题。

并查集主要支持两个操作:
1. 合并(Union):将两个不相交的集合合并成一个集合。
2. 查询(Find):查询元素所在的集合。

并查集可以用于解决一些集合相关的问题,例如判断两个元素是否属于同一个集合,求集合中的元素个数等。

并查集的实现通常使用数组和树结构。数组表示每个元素的父节点,树结构表示集合的层次结构。在进行查找操作时,通过递归或迭代找到根节点;在进行合并操作时,将一个集合的根节点连接到另一个集合的根节点上。

并查集的时间复杂度主要取决于合并和查询操作的路径长度,通常可以达到近似常数时间复杂度。

例如,假设有5个元素分别为1、2、3、4、5,初始时每个元素都是一个单独的集合:
[1, 2, 3, 4, 5]

执行合并操作:将元素1和元素2合并
[2, 2, 3, 4, 5]

执行合并操作:将元素2和元素3合并
[2, 2, 2, 4, 5]

执行查询操作:查询元素1所在的集合
2

执行查询操作:查询元素4所在的集合
4

并查集是一种简单且高效的数据结构,可以在解决某些集合问题时提供方便和效率。

模板:

int find(int x)//查找
{if (f[x] == x) return x;return f[x] = find(f[x]);
}
void merge(int x, int y) //合并
{x = find(x), y = find(y);if (x != y)f[x] = f[y];
}

题目一(合根植物):

代码:

#include<iostream>
using namespace std;
int f[1000010];
int find(int k)//查询父亲
{if (f[k] == k)return k;else{f[k] = find(f[k]);return f[k];}
}
void merge(int a, int b)//合并
int main()
{int n, m;cin >> n >> m;for (int i = 1; i <= n * m; i++)//初始化{f[i] = i;}int k;cin >> k;while (k--){int a, b;cin >> a >> b;merge(a, b);//合并}long long ans=0;for (int i = 1; i <= n * m; i++){if (f[i] == i)//父亲为自己则为一个集合的代表ans++;}cout << ans;
}

题目二(蓝桥幼儿园): 

代码:

#include<iostream>
using namespace std;
int n,m;
int f[200100];
int find(int x)//查找
{if(f[x]==x)return x;return f[x]=find(f[x]);
}
void merge(int x,int y)//合并
{x=find(x),y=find(y);if(x!=y)f[x]=f[y];
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)//初始为自己f[i]=i;while(m--){int x,y,z;cin>>z>>x>>y;if(z==1)//操作一合并{merge(x,y);}else//操作二{if(find(x)==find(y))cout<<"YES"<<endl;elsecout<<"NO"<<endl;}}
}

题目三(小猪存钱罐):

代码:

#include <iostream>//实际上就是几个连通分支
using namespace std;
int n,ans=0;
int f[1001000];
int find(int x)//查找
{if (f[x] == x) return x;return f[x] = find(f[x]);
}
void merge(int x, int y) //合并
{x = find(x),y = find(y);if (x != y) f[x] = f[y];
}
int main()
{cin>>n;for(int i=1;i<=n;i++)f[i]=i;for(int i=1;i<=n;i++){int x;cin>>x;merge(x,i);}for(int i=1;i<=n;i++){if(f[i]==i)//有一样的则为一个集合里的ans++;}cout<<ans;
}

题目四(星球大战):

代码:

#include<iostream>
#include<vector>
using namespace std;
int n, f[500100], ans[500100], m, k,cnt=0;
vector<int> e[500100];
int destroys[500100];
int broken[500100];
int find(int x)//查找
{if (f[x] == x) return x;return f[x] = find(f[x]);
}
void merge(int x, int y) //合并
{x = find(x),y = find(y);if (x != y) f[x] = f[y];
}
int main()
{cin >> n >> m;while (m--){int x, y;cin >> x >> y;e[x].push_back(y), e[y].push_back(x);}cin >> k;for (int i = 0; i < k; i++){cin >> destroys[i];broken[destroys[i]] = 1;//标记为摧毁}for (int i = 0; i < n; i++)//初始化父亲点为自身f[i] = i;for (int i = 0; i < n; i++){if (broken[i])//被摧毁则跳过continue;for (int j = 0; j < e[i].size(); j++)//遍历i点相连的边{int tmp = e[i][j];//相邻的点if (broken[tmp])//被摧毁跳过continue;merge(i, tmp);//合并两点为同一连通块}}for (int i = 0; i < n; i++)//遍历所有城市,先找到所有摧毁完后的连通块数if (!broken[i] && find(i) == i)//该城市没被摧毁且不是自身为父亲节点cnt++;for (int i = k - 1; i >= 0; i--)//从后往前修复道路{ans[i] = cnt;//记录该城市还没被修复时的连通块数量broken[destroys[i]] = 0;//修复该点cnt++;//修复该点,可以成为一个独立的连通分支for (int j = 0; j < e[destroys[i]].size();j++)//遍历该摧毁点的相连边{int v = e[destroys[i]][j];//相邻的点if (!broken[v] && find(v) != find(destroys[i]))//该城市没被摧毁且二者之前不属于同一连通块{merge(v, destroys[i]), cnt--;//因为原本相连,其实二者为同一连通块,合并二者且连通数减一}}}cout << cnt << endl;//完整时的连通块数量for (int i=0;i<k;i++)cout << ans[i] << endl;}

相关文章:

并查集(蓝桥杯 C++ 题目 代码 注解)

目录 介绍&#xff1a; 模板&#xff1a; 题目一&#xff08;合根植物&#xff09;&#xff1a; 代码&#xff1a; 题目二&#xff08;蓝桥幼儿园&#xff09;&#xff1a; 代码&#xff1a; 题目三&#xff08;小猪存钱罐&#xff09;&#xff1a; 代码&#xff1a; …...

MapReduce内存参数自动推断

MapReduce内存参数自动推断。在Hadoop 2.0中&#xff0c;为MapReduce作业设置内存参数非常繁琐&#xff0c;涉及到两个参数&#xff1a;mapreduce.{map,reduce}.memory.mb和mapreduce.{map,reduce}.java.opts&#xff0c;一旦设置不合理&#xff0c;则会使得内存资源浪费严重&a…...

pyside6 pytq PyDracula QVideoWidget视频只有画面没有声音

解决方案&#xff1a; 先不使用框架&#xff0c;纯pyside6代码&#xff0c;如果添加视频有画面有声音&#xff0c;那可以排除是硬件问题&#xff0c;如果没有画面只有声音&#xff0c;可能是视频解码器无法解码&#xff0c;换个格式的视频文件如果只有使用PyDracula 出问题&am…...

Axure基础 各元件的作用及介绍

图像热区 增加按钮或者文本的点击区域&#xff0c;他是透明的&#xff0c;在预览时看不见。 动态面板 用来绘制一下带交互效果的元件&#xff0c;他是动态的&#xff0c;如轮播图&#xff0c;一个动态面板里可以有多个子面板&#xff0c;每一个子面板对应着不同的效果。 他…...

学习Java的第六天

目录 一、变量 1、变量的定义 2、变量的声明格式 3、变量的注意事项 4、变量的作用域 二、常量 三、命名规范 Java 语言支持如下运算符&#xff1a; 1、算术运算符 解析图&#xff1a; 示例&#xff1a; 2、赋值运算符 解析图&#xff1a; 示例&#xff1a; 3、关…...

基于Spring Boot+ Vue的房屋租赁系统

末尾获取源码作者介绍&#xff1a;大家好&#xff0c;我是墨韵&#xff0c;本人4年开发经验&#xff0c;专注定制项目开发 更多项目&#xff1a;CSDN主页YAML墨韵 学如逆水行舟&#xff0c;不进则退。学习如赶路&#xff0c;不能慢一步。 目录 一、项目简介 二、开发技术与环…...

多轨迹建模方法的介绍与实操-基于R语言

本文介绍了多轨迹建模方法&#xff08;Group-Based Multivariate Trajectory Modeling&#xff09;&#xff0c;这是一种扩展了单指标组基轨迹建模的技术&#xff0c;用于分析多个疾病生物标志物或临床重要因素的联合轨迹&#xff0c;以更好地理解和追踪疾病进程、行为或健康状…...

【Spring】Spring状态机

1.什么是状态机 (1). 什么是状态 先来解释什么是“状态”&#xff08; State &#xff09;。现实事物是有不同状态的&#xff0c;例如一个自动门&#xff0c;就有 open 和 closed 两种状态。我们通常所说的状态机是有限状态机&#xff0c;也就是被描述的事物的状态的数量是有…...

Node.js基础---使用Express写接口

1. 创建基本的服务器 2. 创建 API 路由模块 // aoiRouter.js 路由模块 const express require(express) const apiRouter express.Router()module.exports apiRouter// ------------------------------------------// app.js 导入并注册路由模块 const apiRouter require(…...

小蓝的钥匙(蓝桥杯错排)

现在有28个小朋友&#xff0c;每个人手上有一把钥匙&#xff0c;每一个钥匙都只能打开自己的房间门&#xff0c;现在将所有钥匙都收上来&#xff0c;然后再随机打乱分给每个小朋友&#xff0c;也就是有28&#xff01;的分法&#xff0c;请问现在其中14个小朋友的钥匙能恰好打开…...

【Python】科研代码学习:八 FineTune PretrainedModel (用 trainer,用 script);LLM文本生成

【Python】科研代码学习&#xff1a;八 FineTune PretrainedModel [用 trainer&#xff0c;用 script] LLM文本生成 自己整理的 HF 库的核心关系图用 trainer 来微调一个预训练模型用 script 来做训练任务使用 LLM 做生成任务可能犯的错误&#xff0c;以及解决措施 自己整理的 …...

SpringBoot RestTemplate远程调用总结

1、get请求 GetMapping("/searchEntryRecordPageList") public JSONObject searchEntryRecordPageList(RequestParam Map<String,Object> params){HttpHeaders requestHeaders new HttpHeaders();requestHeaders.add("Authorization","Bearer…...

Python 强大邮件处理库 Imbox

目录 IMAP Mailbox Imbox 安装 特性 提取邮件内容 处理附件 安全性 示例 1&#xff1a;读取收件箱中的邮件 2&#xff1a;搜索并下载附件 3&#xff1a;连接到IMAP服务器获取所有邮件 结论 IMAP Mailbox IMAP&#xff08;Internet Message Access Protocol&#x…...

ElasticSearch深度分页问题如何解决

文章目录 概述解决方法深度分页方式from size深度分页之scrollsearch_after 三种分页方式比较 概述 Elasticsearch 的深度分页问题是指在大数据集上进行大量分页查询时可能导致的性能下降和资源消耗增加的情况。这种情况通常发生在需要访问大量数据的情形下&#xff0c;比如用…...

景安空间不支持指定运行目录tp5

/WEB/public/.htaccess配置 <IfModule mod_rewrite.c> Options FollowSymlinks -Multiviews RewriteEngine on RewriteCond %{REQUEST_FILENAME} !-d RewriteCond %{REQUEST_FILENAME} !-f RewriteRule ^(.*)$ index.php?s$1 [QSA,PT,L] </IfModule>. 2./WEB/.ht…...

开放式高实时高性能PLC控制器解决方案-基于米尔电子STM32MP135

前言 随着工业数字化进程加速与IT/OT深入融合&#xff0c;不断增加的OT核心数据已经逐步成为工业自动化行业的核心资产&#xff0c;而OT层数据具备高实时、高精度、冗余度高、数据量大等等特点&#xff0c;如何获取更加精准的OT数据对数字化进程起到至关重要的作用&#xff0c;…...

【MySQL】-MVCC多版本并发控制

1、当前读 select 不加锁状态&#xff0c;当前读快照读 2、快照读 在select加锁下&#xff0c;读取数据后&#xff0c;形成快照。每个事务都会形成自己的快照内容 SELECT * FROM xx_table LOCK IN SHARE MODE;SELECT * FROM xx_table FOR UPDATE;INSERT INTO xx_table ...D…...

mangoDB:2024安装

mangoDB:2024安装 mangoDB: 下载链接 取消勾选 配置环境变量 启动服务 同级目录下创建一个db文件夹 然后执行命令&#xff0c;启动服务 mongod --dbpath D:\environment\mango\db访问http://localhost:27017/ 出现下面的就是安装成功 2然后在管理员权限下给mango服务重…...

微服务day06-Docker

Docker 大型项目组件较多&#xff0c;运行环境也较为复杂&#xff0c;部署时会碰到一些问题&#xff1a; 依赖关系复杂&#xff0c;容易出现兼容性问题 开发、测试、生产环境有差异 1.什么是Docker? 大型项目组件很多&#xff0c;运行环境复杂&#xff0c;部署时会遇到各种…...

喜马拉雅后端一面

1.自我介绍 2.项目拷打 2.1 为什么要用分布式锁&#xff1f; 2.2 用唯一索引能不能保证一人一单&#xff0c;和你的分布式锁比起来怎么用&#xff1f; 2.3 分布式锁是在事务开启前加还是事务开始后 2.4 讲讲你的布隆过滤器是怎么自定义实现的 2.5 讲讲你的Redis和数据库的数据一…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

前端开发者常用网站

Can I use网站&#xff1a;一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use&#xff1a;Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站&#xff1a;MDN JavaScript权威网站&#xff1a;JavaScript | MDN...

手动给中文分词和 直接用神经网络RNN做有什么区别

手动分词和基于神经网络&#xff08;如 RNN&#xff09;的自动分词在原理、实现方式和效果上有显著差异&#xff0c;以下是核心对比&#xff1a; 1. 实现原理对比 对比维度手动分词&#xff08;规则 / 词典驱动&#xff09;神经网络 RNN 分词&#xff08;数据驱动&#xff09…...

性能优化中,多面体模型基本原理

1&#xff09;多面体编译技术是一种基于多面体模型的程序分析和优化技术&#xff0c;它将程序 中的语句实例、访问关系、依赖关系和调度等信息映射到多维空间中的几何对 象&#xff0c;通过对这些几何对象进行几何操作和线性代数计算来进行程序的分析和优 化。 其中&#xff0…...

Qt Quick模块功能及架构

Qt 6.0 中的 Qt Quick 模块是构建现代、动态用户界面的核心框架&#xff0c;基于声明式编程&#xff08;QML&#xff09;和 JavaScript&#xff0c;专注于高性能、流畅的动画和跨平台 UI 开发。、 一、主要功能改进 1. Qt Quick 核心架构 QML 引擎升级&#xff1a;Qt 6.0 使用…...

【论文解读】MemGPT: 迈向为操作系统的LLM

1st author: Charles Packer paper MemGPT[2310.08560] MemGPT: Towards LLMs as Operating Systems code: letta-ai/letta: Letta (formerly MemGPT) is the stateful agents framework with memory, reasoning, and context management. 这个项目现在已经转化为 Letta &a…...