acwing学习笔记 查并集 合并集合 图解

本文主要是介绍acwing学习笔记 查并集 合并集合 图解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

解题的知识背景·森林 树 

作为四大逻辑结构之一的树，我们应该用不同的思维构建模型（不只是链状或者线状）

每个集合视作一棵树构成森林，如图，右子树为兄弟树即为同一层，左子树为孩子

图解：

题目如下

一共有 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，都要输出一个结果，如果 aa 和 bb 在同一集合内，则输出 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

代码如下：

#include<stdio.h>
int die[100010];
int find(int x)
{
	if(die[x] != x)
		die[x] = find(die[x]);
	return die[x];
}
int main()
{
	
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++) die[i] = i;
	while(m --)
	{
		char op[2];
		int a, b;
		scanf("%s%d%d", op, &a, &b);
		if(*op== 'M') die[find(a)] = find(b);
		else
		{
			if(find(a) == find(b)) printf("Yes\n");
			else printf("No\n");
		}
	}
	return 0;
} 

希望能够提供一点帮助，共勉

这篇关于acwing学习笔记 查并集 合并集合 图解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！