一、链接
836. 合并集合
二、题目
一共有 nn 个数,编号是 1∼n1∼n,最开始每个数各自在一个集合中。
现在要进行 mm 个操作,操作共有两种:
-
M a b
,将编号为 aa 和 bb 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作; -
Q a b
,询问编号为 aa 和 bb 的两个数是否在同一个集合中;
输入格式
第一行输入整数 nn 和 mm。
接下来 mm 行,每行包含一个操作指令,指令为 M a b
或 Q a b
中的一种。
输出格式
对于每个询问指令 Q a b
,都要输出一个结果,如果 aa 和 bb 在同一集合内,则输出 Yes
,否则输出 No
。
每个结果占一行。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例:
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例:
Yes
No
Yes
难度:简单 |
时/空限制:1s / 64MB |
总通过数:80710 |
总尝试数:127618 |
来源:模板题,AcWing |
算法标签 |
挑战模式
三、题意
题目的意思比较简单,就是将两个元素合并到同一个集合,然后随便给定两个元素,判断这两个元素是否属于同一个集合
属于模板题目
四、代码
#include<iostream>
using namespace std;
const int N=1e5+10;
int p[N];
int find(int x)
{
if(x!=p[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];
int a,b;
scanf("%s%d%d",op,&a,&b);
if(op[0]=='M')
{
p[find(a)]=find(b);
}
else
{
if(find(a)==find(b))
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
}
return 0;
}
五、总结
1.并查集:实现两种操作,第一种是将两个元素合并到一个集合(改变一个元素的根节点指向另一个元素的根节点即可),第二种是查询给定的两个元素是否属于同一个集合(判断这两个数的根节点是否相同)
2.所以核心就是在根节点上进行操作
3.数据范围是1e5,可以给每一个数据分配一个下标,表示节点,也就是代码里面的初始化操作
for(int i=1;i<=n;i++)
{
p[i]=i;
}
注意这里要从1开始循环,因为题目给的数据从1到n
4.p[]数组现在下标等于数值,给定一个数值可以找到具体的结点是哪一个,因为题目的特殊性质(只需要实现查询两个元素是否属于同一个集合,只需要输出yes/no),所以我们可以进一步优化,让每一个结点直接指向根节点,也就是p[]直接等于根节点的数值,假设根节点是p[3]=3,属于同一个集合的还有,4,5,6,7,那么有p[4],p[5],p[6],p[7]都等于3
5.路径压缩说的就是把所有节点都指向根节点:实现的代码就是这一行:
if(p[x]!=x)
{
p[x]=find(p[x]);
}
迭代的思想,只有根节点的下标等于本身数值,其他的结点的数值都不等于下标(这里是指经过合并操作之后的,初始化之后所有结点,下标都等于数值,也可以理解成最开始有n个根节点,合并操作之后,会把结点的数值进行修改),节点的数值等于根节点的数值,下标表示的是原来这个数字。只有下标和数值相等了,才会返回数值,也就是返回根节点
6.把两个元素合并到同一个集合:让a的根节点指向b的根节点,把a的根节点也修改一遍,那么相应的,所有以a为根节点的结点,都要发生改变,实现的代码是这一行
p[find(a)]=find(b);
find(a)找到的是a的根节点的数值,根据根节点数值和下标相等,p[find(a)]表示的是纯正的根节点,比如p[3]=3这种根节点,把另一个元素的根节点的数值赋给这个元素,表示的是把根节点换了,以前a的根节点现在以前把a的根节点当作根节点的,现在把b的根节点当作根节点,反正就是find函数里面迭代,一直找到下标等于数值的才会停止
7.查询两个元素是否属于同一个集合:直接看他们的根节点是否相等就好了。
8.本质其实挺简单的,但是理解代码感觉还是有些难度,比较绕,既然是模板题目,记住算法思路和写法,然后可以熟练的默写出来就可以了。
六、精美图片
文章来源:https://www.toymoban.com/news/detail-635768.html
文章来源地址https://www.toymoban.com/news/detail-635768.html
到了这里,关于并查集模板-两个操作:合并集合和查询两个元素是否属于同一个集合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!