并查集模板-两个操作：合并集合和查询两个元素是否属于同一个集合

一、链接

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

输入样例：

输出样例：

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.本质其实挺简单的，但是理解代码感觉还是有些难度，比较绕，既然是模板题目，记住算法思路和写法，然后可以熟练的默写出来就可以了。