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

C++:合并集合(并查集)

合并集合

一共有n个数,编号是1~n,最开始每个数各自在一个集合中。
现在要进行m个操作,操作共有2种:
1.“M a b”,将编号为a和b的两个数的所在的集合合并,如果两个数已经在同一个集合中则忽略这个操作
2.“Q a b”,询问编号为a和b的两个数是否在同一个集合中

输入格式

第一行输入整数n和m
接下来m行,每行包含一个操作指令,指令为"M a b"或"Q a b"的一种

输出格式

对于每个询问指令"Q a b",都要输出一个结果,如果a和b在同一集合内则输出"Yes",否则输出"No"
每个结果占一行

数据范围

1 ≤ n , m ≤ 1 0 5 1\le n,m\le 10^5 1n,m105

输入样例

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例

Yes
No
Yes

问题分析

并查集(DSU,Disjoint Set Union)
1.将两个集合合并
2.询问两个元素是否在一个集合中
基本原理:每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个结点存储它的父结点,p[x]表示x的父结点

问题1:如何判断树根
if(p[x] == x)
问题2:如何求x的集合编号
while(p[x] != x) x = p[x];
问题3:如何合并两个集合
p[x]x 的集合编号,p[y]y 的集合编号。p[x] = y

优化:路径压缩

AC代码

#include<iostream>
using namespace std;const int N = 1e5 + 10;int n, m;
int p[N];int find(int x) {	// 返回 x 的祖宗结点 + 路径压缩if(p[x] != x) p[x] = find(p[x]);return p[x];
}int main() {scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) p[i] = i;while(m--) {char op[2];int a, b;scanf("%s%d%d", op, &a, &b);if(op[0] == 'M') p[find(a)] = find(b);else {if(find(a) == find(b)) puts("Yes");else puts("No");}}return 0;
}

相关文章:

C++:合并集合(并查集)

合并集合 一共有n个数&#xff0c;编号是1~n&#xff0c;最开始每个数各自在一个集合中。 现在要进行m个操作&#xff0c;操作共有2种&#xff1a; 1.“M a b”&#xff0c;将编号为a和b的两个数的所在的集合合并&#xff0c;如果两个数已经在同一个集合中则忽略这个操作 2.“…...

【LeetCode】数据结构题解(10)[有效的括号]

有效的括号 &#x1f609; 1.题目来源&#x1f440;2.题目描述&#x1f914;3.解题思路&#x1f973;4.代码展示 &#x1f618;&#x1f618;&#x1f618;&#x1f618;&#x1f618;&#x1f618;&#x1f618;&#x1f618;&#x1f618;&#x1f618;&#x1f618;&#x1…...

5G用户逼近7亿,5G发展迈入下半场!

尽管普遍认为5G投资高峰期正在过去&#xff0c;但是从2023年上半年的情况来看&#xff0c;我国5G建设仍在衔枚疾走。 近日举行2023年上半年工业和信息化发展情况新闻发布会上&#xff0c;工信部人士透露&#xff0c;截至今年6月底&#xff0c;我国5G基站累计达到293.7万个&…...

分布式问题

1. 分布式系统CAP原理 CAP原理&#xff1a;指在一个分布式系统中&#xff0c;Consistency&#xff08;一致性&#xff09;、Availability&#xff08;可用性&#xff09;、Partitontolerance&#xff08;分区容忍性&#xff09;&#xff0c;三者不可得兼。 一致性&#xff08;C…...

教雅川学缠论06-中枢

本系列文章之前讲的内容都只有上升和下降两类趋势&#xff0c;并没有提及盘整&#xff0c;在缠论中&#xff0c;中枢这个新词汇用来定义盘整&#xff0c;中枢&#xff1a; 1.至少由5条线段&#xff08;或笔&#xff09;组成 2.中枢是有方向的&#xff0c;中枢左右两侧外面的线&…...

如何调教让chatgpt读取自己的数据文件(保姆级图文教程)

提示&#xff1a;如何调教让chatgpt读取自己的数据文件(保姆级图文教程) 文章目录 前言一、如何投喂自己的数据&#xff1f;二、调教步骤总结 前言 chatgpt提示不能读取我们提供的数据文件&#xff0c;我们应该对它进行调教。 一、如何投喂自己的数据&#xff1f; 让chatgpt读…...

React Native Camera的使用

介绍 React Native Camera是一个用于在React Native应用中实现相机功能的库。它允许你访问设备的摄像头&#xff0c;并捕获照片和视频。 使用 安装 npm install react-native-camera --save 安装完成后&#xff0c;你需要链接React Native Camera库到你的项目中。可以使用以…...

【Matlab】Elman神经网络遗传算法(Elman-GA)函数极值寻优——非线性函数求极值

往期博客&#x1f449; 【Matlab】BP神经网络遗传算法(BP-GA)函数极值寻优——非线性函数求极值 【Matlab】GRNN神经网络遗传算法(GRNN-GA)函数极值寻优——非线性函数求极值 【Matlab】RBF神经网络遗传算法(RBF-GA)函数极值寻优——非线性函数求极值 本篇博客将主要介绍Elman神…...

@ControllerAdvice注解使用及原理探究 | 京东物流技术团队

最近在新项目的开发过程中&#xff0c;遇到了个问题&#xff0c;需要将一些异常的业务流程返回给前端&#xff0c;需要提供给前端不同的响应码&#xff0c;前端再在次基础上做提示语言的国际化适配。这些异常流程涉及业务层和控制层的各个地方&#xff0c;如果每个地方都写一些…...

Error: Design has unresolved cell reference

我正在「拾陆楼」和朋友们讨论有趣的话题&#xff0c;你⼀起来吧&#xff1f; 拾陆楼知识星球入口 所有的unresolved cell reference问题都是cell信息没读到引起的&#xff0c;在dc/pt里就是db没读到&#xff0c;在ICC2里就是ndm没读。 ICC2中午饭这个问题可以report_design_…...

uni-app 封装api请求

前端封装api请求 前端封装 API 请求可以提高代码的可维护性和重用性&#xff0c;同时使得 API 调用更加简洁和易用。 下面是一种常见的前端封装 API 请求的方式&#xff1a; 创建一个 API 封装模块或类&#xff1a;可以使用 JavaScript 或 TypeScript 创建一个独立的模块或类来…...

SpringCloud实用篇1——eureka注册中心 Ribbon负载均衡原理 nacos注册中心

目录 1 微服务1.1 微服务的演变1.2 微服务1.3 SpringCloud1.4 小结 2 服务拆分及远程调用2.1 服务拆分2.2 服务拆分案例2.3 实现远程调用2.4 提供者与消费者 3 Eureka注册中心3.1 Eureka的结构和作用3.2 搭建eureka-server3.3 服务注册3.4 服务发现 4 Ribbon负载均衡4.1 负载均…...

【MySQL】sql字段约束

在MySQL中&#xff0c;我们需要存储的数据在特定的场景中需要不同的约束。当新插入的数据违背了该字段的约束字段&#xff0c;MySQL会直接禁止插入。 数据类型也是一种约束&#xff0c;但数据类型这个约束太过单一&#xff1b;比如我需要存储的是一个序号&#xff0c;那就不可…...

森海塞尔为 CUPRA 首款纯电轿跑 SUV – CUPRA Tavascan 注入音频魅力

森海塞尔为 CUPRA 首款纯电轿跑 SUV – CUPRA Tavascan 注入音频魅力 音频专家森海塞尔携手富有挑战精神的 CUPRA&#xff0c;雕琢时代新贵车型&#xff0c;打造畅快尽兴的驾驶体验 全球知名音频专家森海塞尔与以颠覆传统、充满激情、不甘现状而闻名的汽车品牌 CUPRA 展开合作…...

Java、Android 加解密、编码、压缩、解压缩、Hash

对称加密&#xff1a; 算法:AES &#xff08;128位&#xff09;/ DES &#xff08;56位&#xff09;....等 加密原理&#xff1a; 原数据--->加密算法(密钥)------>密文 解密原理&#xff1a; 密文---->解密算法(密钥)------>原数据 非对称加密 算法&#…...

11_Pulsar Adaptors适配器、kafka适配器、Spark适配器

2.3. Pulsar Adaptors适配器 2.3.1.kafka适配器 2.3.2.Spark适配器 2.3. Pulsar Adaptors适配器 2.3.1.kafka适配器 Pulsar 为使用 Apache Kafka Java 客户端 API 编写的应用程序提供了一个简单的解决方案。 在生产者中, 如果想不改变原有kafka的代码架构, 就切换到Pulsar的…...

jupyter文档转换成markdown

背景 上一篇文章**《如何优雅地用python生成模拟数据》**我就使用jupyter写的&#xff0c;这个真的是万能的&#xff0c;可以插入markdown格式的内容&#xff0c;也可写代码&#xff0c;关键是像ipython一样&#xff0c;可以分步执行。 我可以这样自由的写我的博客内容&#x…...

日志框架及其使用方法

log4j和logBack,同一个人写的&#xff0c;logBack为log4j的升级版&#xff0c;SpringBoot中默认集成logBack 作用&#xff1a;记录软件发布后的一些bug,以及数据是怎样被操作的 传统开发弊端&#xff1a; 1.日志直接输出在控制台&#xff0c;关闭控制台后&#xff0c;日志消…...

ZIG:理解未来编程语言的视角

文章目录 摘要&#xff1a;引言&#xff1a;性能简洁性和模块化避免常见错误和陷阱总结&#xff1a;参考资料&#x1f4d1;: 摘要&#xff1a; 本文介绍了新兴编程语言ZIG的目标和特点&#xff0c;包括高性能、简洁性和模块化&#xff0c;并分析了这些特点是如何通过语言设计来…...

让三驾马车奔腾:华为如何推动空间智能化发展?

上个月&#xff0c;国务院常务会议审议通过了《关于促进家居消费的若干措施》&#xff0c;其中明确提出了“推动单品智能向全屋智能发展创新培育智能消费”“开展数字家庭建设试点”等推动全屋智能拼配发展的建议与方案。 可以说&#xff0c;以整屋为单位的空间智能品类&#x…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...

车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...

Yii2项目自动向GitLab上报Bug

Yii2 项目自动上报Bug 原理 yii2在程序报错时, 会执行指定action, 通过重写ErrorAction, 实现Bug自动提交至GitLab的issue 步骤 配置SiteController中的actions方法 public function actions(){return [error > [class > app\helpers\web\ErrorAction,],];}重写Error…...