C++代码

#include <iostream>

using namespace std;
const int N = 1e5+5;
int fa[N];
int cnt[N];
int n, m, a, b;
string c;

int get(int x)
{
    if(fa[x] == x) return x;
    return fa[x] = get(fa[x]);
}

void Merge(int x, int y)
{
    int p, q;
    p = get(x); q = get(y);//必须存一下，节点数累加时，累加的是没修改前的
    fa[p] = q;
    cnt[q] += cnt[p];
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) { fa[i] = i; cnt[i] = 1;}

    while(m--)
    {
        cin >> c;
        if(c == "C") {
            cin >> a >> b;
            if(get(a) != get(b)) Merge(a, b);//可能已经连通，判断一下避免重复累加节点数
        }
        if(c == "Q1"){
            cin >> a >> b;
            if(get(a) == get(b)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
        if(c == "Q2"){
            cin >> a;
            cout << cnt[get(a)] << endl;
        }
    }
    return 0;
}