题目描述
一共有 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≤10^5
输入样例:
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例:
Yes
No
Yes
思路:
- 从总体上来看,就是并查集,思想要结合树的双亲表示法
- 刚开始时定义一个数组,数组的下标即表示下标,又表示元素的值(也是集合的编号);如
UFSet[2] = 2
,每一个元素的的值又表示根结点 - 合并操作时,两个不同的集合才能合并,此时需要判断两个集合是否是同一个集合,就要判断他们的根结点是否相同,所以在合并操作时,需要先进行查找操作,查找两个集合的根结点是否相同。
- 查找操作:在操作时主要就是查找根结点,由于
UFSet[2] = 2
的根结点就为2,即在查找时只需要if(UFSet[i] == i)
就能找到根结点
C 代码
#include <stdio.h>
#include <stdlib.h>
//初始化
void Initial(int *UFSet,int n) {
for (int i = 1; i <= n; i++)//从1开始
{
UFSet[i] = i;//最开始每个数各自在一个集合中,并且等于本身的下标数
}
}
//先找到根结点,再压缩路径
int Find(int *UFSet, int x) {
if (UFSet[x] != x)//如果当前结点不是根结点,递归查找
{
UFSet[x] = Find(UFSet, UFSet[x]);//找当前结点的父结点
}
return UFSet[x];//返回根结点
}
int main() {
int m,n,a,b;
char op[2];
scanf("%d%d", &n, &m);
int *UFSet = (int *)malloc(sizeof(int) * n);//申请一片连续的空间,也就是数组
Initial(UFSet,n);
while ( m-- )
{
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'M' && (Find(UFSet, a) != Find(UFSet, b)))
{
/*
例如合并1,2 ;此时UFSet[1] = 1;UFSet[2] = 2
进行合并操作 UFSet[1] = UFSet[2] = 2;此时UFSet[1]的根结点就是2,也就是UFSet[1]集合合并到了
UFSet[2]集合中
但是在合并操作之前,需要查找两集合是否是同一集合
如:
现在UFSet[5] =5表示结合编号为5的集合,假设此时集合编号为5的结合中的元素有1,2,3,
也就是集合{1,2,3,5}
现在要把单个元素集合UFSet[4] = 4合并到集合2中(UFSet[2] =2),要先判断是否是同一集合
首先要找的集合2中的根结点,也就是执行Find(2)操作,
然后UFSet[4] = Find(2);
如果给的结合UFSet[4]中集合不是单个元素,有多个元素的话{4,6,7,8}(假设此时集合编号为7),
也就是UFSet[4]只是该集合中的一个元素,而非是根结点,
则此时要先找到UFSet[4]的根结点,然后合并
即UFSet[Find(4)] = Find(2);
*/
UFSet[Find(UFSet, a)] = Find(UFSet, UFSet[b]);
}
if (op[0] == 'Q')
{
if (Find(UFSet, a) == Find(UFSet, b))
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
}
return 0;
}