题目描述

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

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

C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
Q2 a，询问点 a 所在连通块中点的数量；
输入格式
第一行输入整数 n 和 m。

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

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

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

每个结果占一行。

数据范围
1≤n,m≤105
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例：
Yes
2
3
难度：简单
时/空限制：1s / 64MB
总通过数：9262
总尝试数：18687
来源：模板题
算法标签

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<iostream>
using namespace std;
int n,m;
int p[100010];//并查集集合
int Size[100010];//判断连通块中点的数量数组
int find(int x){//找出树头  路径压缩
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){p[i]=i;Size[i]=1;}
    while(m--){
        char c[3];
        int a,b;
        scanf("%s%d%d",c);
        if(c[0]=='C'){//合并集合  将a集合并入b集合
            if(find(a)!=find(b)){Size[find(b)]+=Size[find(a)];p[find(a)]=find(b);}
        }
        else if(c[1]=='1'){
            if(find(a)==find(b))printf("Yes\n");
            else printf("No\n");
        }
        else{
            printf("%d\n",Size[find(a)]);
        }
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla