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

【数据结构】并查集

目录

一:用途

二:实现    O(1)

三:例题

例题1:集合

例题2:连通图无向

例题3:acwing 240 食物链


 

一:用途

  1. 将两个集合合并
  2. 询问两个元素是否在一个集合当中

二:实现    O(1)

每个集合用一棵树表示,树根的编号就是整个集合的编号。每个节点存储它的父节点,p[x]表示x的父节点。

  1. 问题一:如何判断树根:if(p[x]==x)
  2. 问题二:如何求x的集合编码:while(p[x]!=x)       x=p[x];
  3. 问题三:如何合并两个集合:px是x的集合编码,py是y的集合编码。p[x]=y      //直接将树y插到树x上作为子树。
(1)朴素并查集:int p[N]; //存储每个点的祖宗节点// 返回x的祖宗节点int find(int x){if (p[x] != x) p[x] = find(p[x]);return p[x];}// 初始化,假定节点编号是1~nfor (int i = 1; i <= n; i ++ ) p[i] = i;// 合并a和b所在的两个集合:p[find(a)] = find(b);(2)维护size的并查集:   //需要求集合点的数量int p[N], size[N];//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义,表示祖宗节点所在集合中的点的数量// 返回x的祖宗节点int find(int x)// 初始化,假定节点编号是1~nfor (int i = 1; i <= n; i ++ ){p[i] = i;    size[i] = 1;}// 合并a和b所在的两个集合:size[find(b)] += size[find(a)];p[find(a)] = find(b);(3)维护到祖宗节点距离的并查集:int p[N], d[N];//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离// 返回x的祖宗节点int find(int x){if (p[x] != x){int u = find(p[x]);d[x] += d[p[x]];p[x] = u;}return p[x];}// 初始化,假定节点编号是1~nfor (int i = 1; i <= n; i ++ ){p[i] = i;d[i] = 0;}// 合并a和b所在的两个集合:p[find(a)] = find(b);d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量

三:例题

例题1:集合

一共有 n 个数,编号是 1∼n,最开始每个数各自在一个集合中。

现在要进行 m 个操作,操作共有两种:

M a b,将编号为 a 和 b 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;
Q a b,询问编号为 a 和 b 的两个数是否在同一个集合中;
输入格式

第一行输入整数 n 和 m。

接下来 m 行,每行包含一个操作指令,指令为 M a b 或 Q a b 中的一种。

输出格式

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

每个结果占一行。

数据范围

1≤n,m≤1e5

输入样例:

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

 输出样例:

Yes
No
Yes

 

#include<iostream>using namespace std;const int N = 100010;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()
{cin >> n >> m;for(int i = 1; i <= n; i++) p[i] = i;      //初始化while(m--){char op[2];int a, b;cin >> op >> a >> b;if(*op == 'M') p[find(a)] = find(b);    //合并a和belse {if(find(a) == find(b)) cout << "Yes" << endl;else cout << "No" << endl;}}return 0;
}

例题2:连通图无向

给定一个包含 n 个点(编号为 1∼n1∼n)的无向图,初始时图中没有边。

现在要进行 m 个操作,操作共有三种:

C a b,在点 a 和点 b 之间连一条边,aa 和 b 可能相等;
Q1 a b,询问点 a 和点 b 是否在同一个连通块中,a 和 b可能相等;
Q2 a,询问点 a所在连通块中点的数量;
输入格式

第一行输入整数 n 和 m。

接下来 m行,每行包含一个操作指令,指令为 C a b,Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b,如果 aa 和 bb 在同一个连通块中,则输出 Yes,否则输出 No。

对于每个询问指令 Q2 a,输出一个整数表示点 a 所在连通块中点的数量

每个结果占一行。

数据范围

1≤n,m≤1051≤n,m≤105

输入样例:

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5


输出样例:

Yes
2
3
#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,p[N],sizee[N];
//p[]存储每个点 sizee[]存储根节点所拥有的子节点数
//并查集中的find函数
int find(int 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;sizee[i]=1;//每个节点作为根节点 集合中只有自己一个元素}while(m--){char op[3];int a,b;scanf("%s",op);if(op[0]=='C')//连边,就是合并{scanf("%d%d",&a,&b);if(find(a)==find(b)) continue;//在一个集合里 就跳出sizee[find(b)]+=sizee[find(a)];//将节点数加到新根节点数上//例如原来a连通块里有3个节点 b里面有4个节点//a连到b的连通块里 那么b里面现在有7个节点p[find(a)]=find(b);//根节点等于b的根节点}else if(op[1]=='1'){scanf("%d%d",&a,&b);if(find(a)==find(b)) puts("Yes");//在同一个集合else puts("No");}else{scanf("%d",&a);printf("%d\n",sizee[find(a)]);//输出根节点的数}}return 0;	
} 

例题3:acwing 240 食物链

相关文章:

【数据结构】并查集

目录 一&#xff1a;用途 二&#xff1a;实现 O(1) 三&#xff1a;例题 例题1&#xff1a;集合 例题2&#xff1a;连通图无向 例题3&#xff1a;acwing 240 食物链 一&#xff1a;用途 将两个集合合并询问两个元素是否在一个集合当中 二&#xff1a;实现 O(1) 每…...

软考--网络攻击分类

网络攻击的主要手段包括口令入侵、放置特洛伊木马程序、拒绝服务&#xff08;DoS)攻击、端口扫描、网络监听、欺骗攻击和电子邮件攻击等。口令入侵是指使用某些合法用户的账号和口令登录到目的主机&#xff0c;然后再实施攻击活动。特洛伊木马&#xff08;Trojans)程序常被伪装…...

蓝桥杯刷题冲刺 | 倒计时17天

作者&#xff1a;指针不指南吗 专栏&#xff1a;蓝桥杯倒计时冲刺 &#x1f43e;马上就要蓝桥杯了&#xff0c;最后的这几天尤为重要&#xff0c;不可懈怠哦&#x1f43e; 文章目录1.长草2.分考场1.长草 题目 链接&#xff1a; 长草 - 蓝桥云课 (lanqiao.cn) 题目描述 小明有一…...

冲击蓝桥杯-并查集,前缀和,字符串

目录 前言 一、并查集 1、并查集的合并&#xff08;带路径压缩&#xff09; 2、询问是否为同一个集合 3、例题 二、前缀和 1 、前缀和是什么 2、经典题目 三- 字符串处理 1、字符串的插入 2、字符串转化为int类型 3、字符反转 前言 并查集合前缀&#xff0c;字符串…...

【matlab学习笔记】线性方程组求解方法

线性方程组求解方法2.1 求逆法实现方式例子2.2 分解法LU分解&#xff08;Doolittle分解&#xff09;实现方法例子QR分解法实现方法例子Cholesky 分解法实现方法例子奇异值分解法实现方法例子Hessenberg 分解实现方法例子Schur 分解实现方法例子2.3 迭代法逐次迭代法里查森迭代法…...

Python带你一键下载到最新章节,不付费也能看

前言 大家早好、午好、晚好吖 ❤ ~欢迎光临本文章 完整源码、素材皆可点击文章下方名片获取此处跳转 开发环境: python 3.8 运行代码 pycharm 2022.3 辅助敲代码 requests 发送请求/第三方模块 模块安装&#xff1a;win R 输入cmd 输入安装命令 pip install 模块名 如果…...

【sentinel】熔断降级规则详解及源码分析

概述 除了流量控制以外&#xff0c;对调用链路中不稳定的资源进行熔断降级也是保障高可用的重要措施之一。一个服务常常会调用别的模块&#xff0c;可能是另外的一个远程服务、数据库&#xff0c;或者第三方API等。例如&#xff0c;支付的时候&#xff0c;可能需要远程调用银联…...

ffplay源码分析-main函数入口分析

ffplay源码分析-main函数入口分析 基于ffmpeg6.0源码分析。 流程 使用ffplay播放视频文件&#xff0c;会触发main函数的调用。main函数中会进行以下操作&#xff1a; 从命令行中解析日志级别、日志是否需要落文件、是否要输出banner信息。banner信息包含版权、库的版本。注…...

C++三种继承方式

C继承的一般语法为&#xff1a;class 派生类名:&#xff3b;继承方式&#xff3d; 基类名{派生类新增加的成员};继承方式限定了基类成员在派生类中的访问权限&#xff0c;包括 public&#xff08;公有的&#xff09;、private&#xff08;私有的&#xff09;和 protected&#…...

【Android -- 软技能】《软技能:代码之外的生存指南》之好书推荐(一)

前言 这是一本由美国的一个软件开发人员写的&#xff0c;但书中除了有 Java 、C# 几个单词外&#xff0c;没有一行代码。 因为这本书讲的是代码之外的东西。 文章目录结构&#xff1a; 1. 职业 从业心态&#xff1a;说白了就是要有责任心&#xff0c;把每份工作要当成是自…...

Nginx可视化管理工具 - Nginx Proxy Manager

一、介绍 nginx-proxy-manager 是一个反向代理管理系统,它基于Nginx,具有漂亮干净的 Web UI。还可以获得受信任的 SSL 证书,并通过单独的配置、自定义和入侵保护来管理多个代理。 其官网地址如下: https://nginxproxymanager.com/ 二、安装 第一步:192.168.1.108服务…...

https是如何保证安全的

在学习http与https的区别的时候&#xff0c;我们通常从以下几点出发&#xff1a;http是超文本传输协议&#xff0c;是明文传输&#xff0c;有安全风险&#xff0c;https在TCP和http网络层之间加入了SSL/TLS安全协议&#xff0c;使得报文能够加密传输http连接简单&#xff0c;三…...

ubuntu下使用GCC开发单片机的过程

以下是一个简单的单片机C程序示例,实现的功能是控制LED灯的闪烁: #include <reg52.h> // 导入单片机的寄存器定义void main() {while(1) { // 无限循环P1 = 0x00; // P1口输出低电平delay(1000); // 延时1秒P1 = 0xff; // P1口输出高电平delay(1000); // 延时1秒…...

人工智能能否取代软硬件开发工程师

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl 人工智能发展趋势 随着AI技术的不断发展&#xff0c;它正在改变我们的生活方式、商业模式和工作方式。人工智能技术的发展一直处于快速变化和持续创新的状态&#xff0c;以下…...

BPI-R3开发板 - uboot编译

一. 获取源码 https://github.com/mtk-openwrt/u-boot 二. 编译步骤 编译环境为ubuntu 18.04。交叉编译工具链我用的是openwrt编译生成的工具链&#xff0c;并设置到环境变量&#xff0c;如下&#xff1a; export PATH$PATH:/root/mt8976/BPI-R3-OPENWRT-V21.02.3-main/staging…...

优秀程序员的5个特征,你在第几层?

每个人程序员都对未来的职业发展有着憧憬和规划&#xff0c;要做架构师、要做技术总监、要做CTO。但现实总是复杂的&#xff0c;日复一日的工作与生活总能让人一次又一次地陷入迷茫。大部分原因就是对职业发展轨迹和自我能力提升的一般规律缺乏认识&#xff0c;做事找不到方向或…...

JAVA Session会话 Thymeleaf - 视图模板技术配置步骤

JAVAWebSession会话会话跟踪技术session保存作用域Thymeleaf - 视图模板技术配置过程Session会话 HTTP是无状态的&#xff1a;服务器无法区分这两个请求是同一个客户端发过来的&#xff0c;还是不同的客户端发过来的 现实问题&#xff1a;第一次请求是添加商品到购物车&#x…...

Linux编译cpprestsdk库

本文用的Linux系统为Ubuntu22.04&#xff0c;自带GCC11.3.0。 依赖 ①编译需要boost库&#xff0c;本文用的库版本为boost-1.82.0.beta1.tar.gz。 ②编译需要openssl库&#xff0c;这里使用的版本为openssl-1.1.1s.tar.gz。 ③编译需要cmake库&#xff0c;本文使用的是cmake-3…...

算法的时间复杂度和空间复杂度

目录 1 如何衡量一个算法的好坏 2.时间复杂度 2.1 时间复杂度的概念 2.2 大O的渐进表示法 2.3常见代码举例 2.3.1 Func2 O(N) 2.3.2 Func3 O(MN) 2.3.3 Func4 O(1) 2.3.4 Func5 strchr O(N) 2.3.5 Func6 冒泡排序 O(N^2) 2.3.6 Func7 二分…...

基本认识vue3

一、基本搭建 项目搭建 使用 最新的 Vue3 TS Vite项目 执行命令 &#xff08;本项目采用如下方式&#xff09; npm create vitelatest my-vite-app --template vue-ts或者 运行项目 npm install npm run dev项目搭建初始化目录 新搭建的项目可能会遇到个问题&#xf…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...

C++_哈希表

本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、基础概念 1. 哈希核心思想&#xff1a; 哈希函数的作用&#xff1a;通过此函数建立一个Key与存储位置之间的映射关系。理想目标&#xff1a;实现…...