并查集模板的应用：连通块

一、链接

837. 连通块中点的数量

二、题目

给定一个包含 nn 个点（编号为 1∼n1∼n）的无向图，初始时图中没有边。

现在要进行 mm 个操作，操作共有三种：

C a b，在点 aa 和点 bb 之间连一条边，aa 和 bb 可能相等；
Q1 a b，询问点 aa 和点 bb 是否在同一个连通块中，aa 和 bb 可能相等；
Q2 a，询问点 aa 所在连通块中点的数量；

输入格式

第一行输入整数 nn 和 mm。

接下来 mm 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b，如果 aa 和 bb 在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 aa 所在连通块中点的数量

每个结果占一行。

数据范围

1≤n,m≤1051≤n,m≤105

输入样例：

输出样例：

Yes
2
3

三、题意

如果两个点之间是连接的，就表示这两个点构成了一个连通块，连通块是原图的子图，子图之外没有点和子图内部的点有联系，也就是说子图之外只要有一个点和子图有联系，就会形成一个新的子图。

我们需要进行多次操作，C是合并两个元素，Q1是查询是否是同一个集合，Q2是查询有多少个元素属于这个集合

四、代码

#include<iostream>

using namespace std;

const int N=1e5+10;

int p[N],si[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;
        si[i]=1;
    }
    
    while(m--)
    {
        char op[2];
        int a,b;
        
        scanf("%s",op);
        if(op[0]=='C')
        {
            scanf("%d%d",&a,&b);
            a=find(a),b=find(b);
            if(a==b)
            {
                continue;
            }
            p[a]=b;
            si[b]+=si[a];
        }
        else if(op[1]=='1')
        {
            scanf("%d%d",&a,&b);
            if(find(a)==find(b))
            {
                printf("Yes\n");
            }
            else
            {
                printf("No\n");
            }
        }
        else
        {
            scanf("%d",&a);
            printf("%d\n",si[find(a)]);
        }
    }
    
    return 0;
}

五、总结

1.并查集的简单应用，做出这道题目最好不要在脑子里面模拟，初学或者不熟悉题型，最好还是在纸上详细模拟实现，寻找他应该使用什么算法，然后把算法模板应用上去，比如说这道题目就是处理两个元素，最开始两个元素是孤立的，后面把两个元素合并到一个集合（连通块），判断两个元素是不是连通块其实就是判断两个元素是不是属于同一个集合，连通块大小的话，直接把大小存在根节点，维护根节点的大小即可。

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

3.什么是连通块：连通块概念

4.continue的作用：continue

5.continue在这里的作用：a和b两个元素相等的话，就不把两个元素的根节点的size更新，因为更新的话就会变成原来的两倍，但是根据实际情况，在这里是不需要更新的，注意这里如果两个元素属于同一个连通块的话，也是需要直接跳出后续的合并步骤的（不仅仅是两个元素相等，操作完之后再出现操作过的数字，还是不再需要处理）

6.把a和b的根节点先取出来，a的根节点更新之后会和b的根节点重合，那时再去维护size将会发生错误，所以要么把根节点取出来，要么先更新size再更新根节点

7.熟练应用，熟能生巧