【七十九】【算法分析与设计】并查集模板!!!并查集的实现_牛客题霸_牛客网,【模板】并查集 - 洛谷,并查集代码!!!

本文主要是介绍【七十九】【算法分析与设计】并查集模板!!!并查集的实现_牛客题霸_牛客网,【模板】并查集 - 洛谷,并查集代码!!!,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

并查集的实现_牛客题霸_牛客网

描述

给定一个没有重复值的整形数组arr,初始时认为arr中每一个数各自都是一个单独的集合。请设计一种叫UnionFind的结构,并提供以下两个操作。

boolean isSameSet(int a, int b): 查询a和b这两个数是否属于一个集合

void union(int a, int b): 把a所在的集合与b所在的集合合并在一起,原本两个集合各自的元素以后都算作同一个集合

[要求]

如果调用isSameSet和union的总次数逼近或超过O(N),请做到单次调用isSameSet或union方法的平均时间复杂度为O(1)

输入描述:

第一行两个整数N, M。分别表示数组大小、操作次数 接下来M行,每行有一个整数opt 若opt = 1,后面有两个数x, y,表示查询(x, y)这两个数是否属于同一个集合 若opt = 2,后面有两个数x, y,表示把x, y所在的集合合并在一起

输出描述:

对于每个opt = 1的操作,若为真则输出"Yes",否则输出"No"

示例1

输入:

4 5 1 1 2 2 2 3 2 1 3 1 1 1 1 2 3

复制

输出:

No Yes Yes

复制

说明:

每次2操作后的集合为 ({1}, {2}, {3}, {4}) ({1}, {2, 3}, {4}) ({1, 2, 3}, {4})

备注:

1 \leqslant N, M \leqslant 10^61⩽N,M⩽106

保证1 \leqslant x, y \leqslant N保证1⩽x,yN

1.

递归转化为迭代,_find的递归写法转化为迭代的写法.

递归的出口是father[i]==i,所以while循环的入口在递归的出口条件前面加上一个!取反.

递归的进入下一层本来是_find(father[i]).转化为迭代就是i=father[i].

中间清理栈的迭代过程也可以想象成是递归的过程.

 
#include<bits/stdc++.h> // 引入常用的头文件
#define int long long // 定义int为长整型,以支持大数据量的处理
#define endl '\n' // 定义换行符为'\n',增加输出速度
#define p pair< long long, long long> // 定义pair类型的别名p,用于存储两个长整型的数值using namespace std; // 使用标准命名空间const int dx[] = { 1, -1, 0, 0 }; // 定义数组dx,用于某些方向操作,此处可能未使用
const int dy[] = { 0, 0, 1, -1 }; // 定义数组dy,用于某些方向操作,此处可能未使用// 全局变量定义区域
int n, m; // n表示数组大小,m表示操作次数
int op, nums1, nums2; // op操作类型,nums1和nums2操作数vector<int> father; // 并查集数组,存储每个元素的父节点
vector<int> _stack; // 辅助栈,用于路径压缩int _find(int i) { // 并查集查找操作,带路径压缩while (!(father[i] == i)) { // 如果i不是自己的父节点,进行路径压缩i = father[i];_stack.push_back(i); // 将当前节点添加到栈中}while (_stack.size()) { // 当栈不为空时,进行路径压缩father[_stack.back()] = i; // 将栈中的每个元素的父节点设置为根节点i_stack.pop_back(); // 弹出栈顶元素}return i; // 返回根节点
}int isSameSet(int x, int y) { // 检查两个元素是否属于同一个集合return _find(x) == _find(y); // 通过查找根节点来判断
}void _union(int x, int y) { // 并查集合并操作if (_find(x) == _find(y)) { // 如果x和y已经属于同一个集合,则不操作return;} else {father[_find(x)] = _find(y); // 将x的根节点的父节点设置为y的根节点,完成合并}
}void init() { // 读取操作和操作数cin >> op >> nums1 >> nums2;
}void solveinit() { // 初始化解决方案,此处未使用
}void solve() { // 根据操作类型执行相应的并查集操作solveinit();if (op == 1) { // 如果是查询操作if (isSameSet(nums1, nums2))cout << "Yes" << endl; // 如果属于同一个集合,输出"Yes"else cout << "No" << endl; // 否则输出"No"} else { // 如果是合并操作_union(nums1, nums2); // 合并nums1和nums2所在的集合}
}signed main() { // 主函数ios::sync_with_stdio(false); // 禁用C和C++的同步,加速cin和coutcin.tie(nullptr); // 解除cin和cout的绑定cout.tie(nullptr);cout << fixed << setprecision(15); // 设置浮点数输出的精度cin >> n >> m; // 读入数组大小和操作次数father.assign(n + 1, 0); // 初始化father数组,大小为n+1for (int i = 0; i <= n; i++) { // 将每个元素的父节点初始化为自己father[i] = i;}while (m--) { // 读取m个操作并执行init();solve();}
}

【模板】并查集 - 洛谷

【模板】并查集

题目描述

如题,现在有一个并查集,你需要完成合并和查询操作。

输入格式

第一行包含两个整数 $$N,$$ ,表示共有 $$$$ 个元素和 $$$$ 个操作。

接下来 $$$$ 行,每行包含三个整数 $$Z_i,X_i,Y_$$ 。

当 $$Z_i=$$ 时,将 $$X_$$ 与 $$Y_$$ 所在的集合合并。

当 $$Z_i=$$ 时,输出 $$X_$$ 与 $$Y_$$ 是否在同一集合内,是的输出

Y ;否则输出 N

输出格式

对于每一个 $$Z_i=$$ 的操作,都有一行输出,每行包含一个大写字母,为 Y 或者 N

样例 #1

样例输入 #1

4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4

样例输出 #1

N Y N Y

提示

对于 $$30\$$ 的数据,$N \le 10$,$M \le 20$。

对于 $$70\$$ 的数据,$N \le 100$,$M \le 10^3$。

对于 $$100\$$ 的数据,$1\le N \le 10^4$,$1\le M \le 2\times 10^5$,$1 \le X_i, Y_i \le N$,$Z_i \in \{ 1, 2 \}$。

 
#include<bits/stdc++.h> // 引入常用的头文件
#define int long long // 定义int为长整型,适用于处理大数据
#define endl '\n' // 定义结束符为'\n',优化输出效率
#define p pair<long long, long long> // 定义pair的别名p,用于存储长整型的键值对using namespace std;const int dx[] = {1, -1, 0, 0}; // 方向数组,可能用于处理四方向问题,本代码未用到
const int dy[] = {0, 0, 1, -1}; // 方向数组,可能用于处理四方向问题,本代码未用到
//----------------------------------------------------int n, m; // n是元素数量,m是操作次数
int op, nums1, nums2; // op是操作类型,nums1和nums2是操作的元素vector<int> father; // 并查集的父节点数组
vector<int> _st; // 辅助栈,用于路径压缩int _find(int i) { // 查找根节点,并应用路径压缩while (!(father[i] == i)) { // 如果节点i不是自己的父节点,继续向上查找_st.push_back(i); // 将当前节点加入栈中i = father[i]; // 移动到父节点}while (_st.size()) { // 路径压缩,将路径上的所有节点直接连接到根节点father[_st.back()] = i;_st.pop_back();}return i; // 返回根节点
}bool isSameSet(int x, int y) { // 判断两个元素是否在同一集合中return _find(x) == _find(y);
}void _union(int x, int y) { // 合并两个集合if (_find(x) == _find(y)) { // 如果已经在同一集合中,则无需合并return;} else {father[_find(x)] = _find(y); // 否则,将一个集合的根节点指向另一个集合的根节点}
}// 初始化函数,读取输入并初始化并查集
void init() {cin >> n >> m;father.assign(n + 1, 0); // 分配并初始化并查集数组for (int i = 0; i <= n; i++) {father[i] = i; // 初始化时,每个元素的父节点是自己}
}// 根据操作类型执行相应的并查集操作
void solve() {if (op == 1) { // 如果是合并操作_union(nums1, nums2);} else { // 如果是查询操作if (isSameSet(nums1, nums2)) cout << "Y" << endl; // 如果在同一集合,输出Yelse cout << "N" << endl; // 否则输出N}
}signed main() {ios::sync_with_stdio(false); // 提高cin和cout的效率cin.tie(nullptr); // 解绑cin和coutcout.tie(nullptr);cout << fixed << setprecision(15); // 设置浮点数精度//----------------------------------------------init(); // 初始化while (m--) { // 处理每个操作cin >> op >> nums1 >> nums2;solve();}
}

结尾

最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。

同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。

谢谢您的支持,期待与您在下一篇文章中再次相遇!

这篇关于【七十九】【算法分析与设计】并查集模板!!!并查集的实现_牛客题霸_牛客网,【模板】并查集 - 洛谷,并查集代码!!!的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/967220

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

Go标准库常见错误分析和解决办法

《Go标准库常见错误分析和解决办法》Go语言的标准库为开发者提供了丰富且高效的工具,涵盖了从网络编程到文件操作等各个方面,然而,标准库虽好,使用不当却可能适得其反,正所谓工欲善其事,必先利其器,本文将... 目录1. 使用了错误的time.Duration2. time.After导致的内存泄漏3. jsO

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制,确认复制是否成功4.同