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

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

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

描述

给定一个没有重复值的整形数组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

相关文章

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

python实现svg图片转换为png和gif

《python实现svg图片转换为png和gif》这篇文章主要为大家详细介绍了python如何实现将svg图片格式转换为png和gif,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录python实现svg图片转换为png和gifpython实现图片格式之间的相互转换延展:基于Py

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl