46、【树和二叉树】并查集——合并集合 (C/C++版)
2023-09-11 14:20:01 时间
一、介绍
并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。
并查集的思想是用一个数组表示了整片森林(parent),树的根节点唯一标识了一个集合,我们只要找到了某个元素的树根,就能确定它在哪个集合里。
它支持查找和合并集合操作,通过并查集这种数据结构可实现对集合数据进行高效的管理。
并查集的基本操作过程图示:
二、实战例题
一共有 n 个数,编号是 1∼n,最开始每个数各自在一个集合中。
现在要进行 m个操作,操作共有两种:
(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≤105
输入样例:
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例:
Yes
No
Yes
三、算法实现
通过根的核心特征进行实现——根的父节指针指向自身
#include <stdio.h>
const int N = 1e5 + 10;
int p[N]; // P[x]为x的父节点下标
int find(int x){ // 返回祖宗节点+路径压缩
// 只有根节点才指向自己,不为根节点时,查找x所在的祖先节点的根节点
if(p[x] != x) p[x] = find(p[x]);
// 将这个集合内的数的根节点均标位x的祖宗
return p[x];
}
int main(){
int n, m; scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) p[i] = i;
while(m--){
char op[2]; // scanf读字符串时会自动忽略空格和回车
int a, b;
scanf("%s%d%d", op, &a, &b);
if(op[0] == 'M')
p[find(a)] = find(b); // 将a集合合并到b集合里
else if(op[0] == 'Q')
// if(find(a) == find(b)) puts("Yes");
// else puts("No");
find(a) == find(b) ? puts("Yes") : puts("No");
}
return 0;
}
时间复杂度:
无注释代码
#include <stdio.h>
const int N = 1e5 + 10;
int p[N];
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main(){
int n, m; scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) p[i] = i;
while(m--){
char op[2]; scanf("%s", op);
int a, b; scanf("%d%d", &a, &b);
if(*op == 'M'){
if(find(a) != find(b)) p[find(a)] = find(b);
}else{
find(a) == find(b) ? puts("Yes") : puts("No");
}
}
return 0;
}
相关文章
- C++之虚函数与虚继承详解
- C++第15周(春)项目2 - 用文件保存的学生名单
- 用链表解决if语句过多的问题(C/C++实现)
- [c++菜鸟]《Accelerate C++》习题解答
- c++用WinForm做界面的实现
- 开源免费的C/C++网络库(c/c++ sockets library)补充
- 《C++覆辙录》——2.2:捉摸不定的评估求值次序
- 基于C++实现(控制台)二叉树和赫夫曼树的建立存储表示及其基本操作【100010610】
- 基于C++实现集合的关系性质计算器【100010522】
- [第十届蓝桥杯省赛C++A/B组]完全二叉树的权值
- 纪念逝去的岁月——C/C++排序二叉树
- 《c++语言导学》——第1章 基 础 知 识1.1 引言
- 113、【树与二叉树】leetcode ——538. 把二叉搜索树转换为累加树:递增数组视角右中左遍历(C++版本)
- 109、【树与二叉树】leetcode ——701. 二叉搜索树中的插入操作:递归法+双指针迭代法(C++版本)
- 108、【树与二叉树】leetcode ——235. 二叉搜索树的最近公共祖先:普通树解法+BST性质解法(C++版本)
- 107、【树与二叉树】leetcode ——236. 二叉树的最近公共祖先:回溯法(C++版本)
- 103、【树与二叉树】leetcode ——700. 二叉搜索树中的搜索:递归法+迭代法(C++版本)
- 99、【树与二叉树】leetcode ——113. 路径总和 II:回溯法两种版本(C++版本)
- 92、【树与二叉树】leetcode ——111. 二叉树的最小深度:层次遍历+先序DFS+后序DFS[子问题分解](C++版本)
- 88、【树与二叉树】leetcode ——226. 翻转二叉树:先中后序的递归与DFS非递归遍历+BFS层次遍历(C++版本)
- 55、【图】Dijkstra求最短路径(单源最短路径+边权重为正数)(C/C++版)
- C++ sort vector<vector<int> > or vector<MyClass> 容器的排序