一. 题目

二. 理论

三. 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
const int N=1e5+10;

int n, m;

class JoinSet
{
public://cnt[i]是i节点所在的集合中点的数量
    int p[N], cnt[N];//p[i]是点i节点的父亲，根的父亲是自己
public:
    JoinSet()
    {
        initIO();
    }

    void initIO()
    {
        // 关闭输入输出缓存，使效率提升
        ios::sync_with_stdio(false);
        // 解除cin和cout的默认绑定，来降低IO的负担使效率提升
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    void init()
    {
        for(int i=1;i<=n;++i)
            p[i]=i, cnt[i]=1;
    }

    //合并b的集合到a集合中
    void add(int a, int b)
    {
        a=find(a), b=find(b);//找根
        if(a==b) return;//已经是同一集合
        p[b]=a, cnt[a]+=cnt[b];//更新
    }

    //查找点x所在集合的树根代表节点, 一旦查找过一遍，则路径上所有点都指向根
    int find(int x)
    {//若当前点不是祖宗节点, 且当前点的父节点不是祖宗节点, 向上寻找
        if(p[x]!=x&&p[x]!=p[p[x]])
            p[x]=find(p[x]);
        return p[x];
    }
}js;

int main()
{
    cin>>n>>m;
    js.init();

    while(m--)
    {
        string op;
        int a, b;

        cin>>op;
        if(op=="C")
        {
            cin>>a>>b;
            js.add(a, b);
        }
        else if(op=="Q1")
        {
            cin>>a>>b;
            if(js.find(a)==js.find(b)) cout<<"Yes";
            else cout<<"No";
            cout<<endl;
        }
        else if(op=="Q2")
        {
            cin>>a;
            cout<<js.cnt[js.find(a)]<<endl;
        }
    }
}