连通块中点的数量

题目

给定一个包含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

分析

这个题是用并查集来保存额外信息的，来保存每个连通块中点的个数
先开一个size数组用来保存每个连通块中的数量，起初每个连通块中的点的数量都是一。这里size数组里保存的都是每一个点祖先所在的连通块的数量

代码

#include<iostream>
using namespace std;
int fa[123456],si[123456];

int find(int x)
{
    if(fa[x]!=x) fa[x]=find(fa[x]);  //路径压缩
    return fa[x];
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) 
    {  //初始化
        fa[i]=i;
        si[i]=1;
    }
    while(m--)
    {
        string s;
        int a,b;
        cin>>s;
        if(s=="C") 
        {
            cin>>a>>b;
            a=find(a),b=find(b);
            if(a!=b)  //如果a和b不在一个连通块中
            {    //将a的祖先置为b，同时b应该加上a中连通块的数量
                fa[a]=b;
                si[b]+=si[a];
            }
        }
        else if(s=="Q1")
        {
            cin>>a>>b;
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else if(s=="Q2") 
        {
            cin>>a; //先找到祖先，然后返回size
            cout<<si[find(a)]<<endl;
        }
    }
    return 0;
}