电商网站春节放假通知,c语言软件开和网站开发区别,有谁有做卫生纸巾的网站,广州seo优化外包公司文章目录 836. 合并集合题目描述并查集acwing并查集模板 836. 合并集合
题目描述
一共有 n 个数#xff0c;编号是 1∼n#xff0c;最开始每个数各自在一个集合中。
现在要进行 m 个操作#xff0c;操作共有两种#xff1a;
M a b#xff0c;将编号为 a 和 b 的两个数… 文章目录 836. 合并集合题目描述并查集acwing并查集模板 836. 合并集合
题目描述
一共有 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≤105
输入样例
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4输出样例
Yes
No
Yes并查集
对并查集算法不太了解的可以看我这篇博客并查集算法
这段代码是一个使用并查集(disjoint set union, DSU)算法实现的集合合并查询系统。并查集是一种数据结构它提供了两个主要功能找到某个元素所在的集合的代表元素(find)以及合并两个元素所在的集合(union)。
#includebits/stdc.h // 引入常用头文件
using namespace std;const int z1e510; // 定义常量z为100010用于数组fa的大小略大于题目中的数据范围1≤n≤10^5int fa[z]; // 定义数组fafa[i]表示编号为i的元素的父节点初始化时每个元素的父节点是它自己// find函数用于找到i的根节点代表元素
int find(int i)
{// 如果i的父节点是它自己说明i就是根节点if(fa[i]i)return i;else{// 否则递归地找到i的根节点并进行路径压缩fa[i]find(fa[i]);return fa[i];}
}// unionn函数用于合并i和j所在的集合
void unionn(int i,int j)
{int i_fafind(i); // 找到i的根节点int j_fafind(j); // 找到j的根节点// 将i的根节点的父节点设置为j的根节点实现合并fa[i_fa]j_fa;
}int main()
{int n,m; // n表示元素个数m表示操作次数cinnm; // 读入n和mfor(int i1;in;i) // 初始化fa数组使每个元素的父节点是它自己fa[i]i;char op[2]; // 定义字符数组op用于存储操作符while(m--) // 循环读入m个操作{char op; // 重新定义op变量用于存储当前操作符int a,b; // a和b用于存储操作的两个数cinopab; // 读入操作符和操作数if(opM) // 如果操作是M执行合并操作unionn(a,b);else // 如果操作是Q执行查询操作{// 如果a和b的根节点相同输出Yes表示a和b在同一集合中if(find(a)find(b)) coutYesendl;else coutNoendl; // 否则输出No}}return 0;
}这个代码实现了并查集的基本操作并应用于解决了一个动态集合合并和查询问题。通过递归的find函数实现了路径压缩提高了查找根节点的效率。union函数通过修改父节点指针来合并两个集合。主函数中通过读入操作利用这两个函数处理合并和查询请求最后输出每次查询的结果。
acwing并查集模板
这段代码实现了一个简单的并查集(Union-Find)数据结构应用用于处理集合的合并(M)和查询(Q)操作。并查集是一种数据结构主要用于处理一些不交集的合并及查询问题。其核心思想是通过每个节点指向其父节点从而形成一个树结构来表示一个集合。树的根节点代表了整个集合通过路径压缩等技术可以高效地进行查找和合并操作。
#includebits/stdc.h // 包含STL库
using namespace std;const int N100010; // 预定义大小足够容纳题目中的最大数据量
int u[N]; // u数组用于表示每个元素的父节点// find函数用于找到x的根节点实现路径压缩
int find(int x) {if(x!u[x]) u[x]find(u[x]); // 如果x不是根节点递归地找到根节点并进行路径压缩return u[x]; // 返回根节点
}int main() {int n,m; // n代表元素个数m代表操作次数cinnm; // 输入n和mfor(int i1;in;i) u[i]i; // 初始化每个元素自成一集合父节点指向自己char op; // 操作类型M或Qint a,b; // 操作涉及的元素while(m--) { // 循环处理所有操作cinopab; // 输入操作和操作数if(opM) {// 如果是合并操作将a的根节点的父节点设置为b的根节点// 从而实现两个集合的合并u[find(a)]find(b);} else {// 如果是查询操作if(find(a)find(b)) coutYes\n; // 如果a和b有相同的根节点则它们在同一个集合中else coutNo\n; // 否则不在同一个集合中}}return 0;
}这段代码的关键在于高效地实现查找和合并操作。查找操作通过递归实现路径压缩即在查找根节点的过程中将路径上的每个节点直接连接到根节点从而减少后续查找的时间。合并操作简单直接只需要将一个集合的根节点指向另一个集合的根节点。查询操作则是通过比较两个元素的根节点是否相同来判断它们是否属于同一个集合。
这样的实现保证了在几乎所有情况下的高效性使并查集成为处理动态连通性问题的有力工具。
