题目描述

代码题：并查集统计联通块中的数量

C++代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int p[N], n, m, s[N];

int find(int x){
    if(p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        p[i] = i;
        s[i] = 1;
    }
    string op;
    int a, b;
    while(m--){
        cin >> op;
        if(op == "C"){
            scanf("%d%d", &a, &b);
            if(find(a) == find(b)) //这步很关键，万一 a == b 避免个数统计错误~
                continue;
            s[find(a)] += s[find(b)];
            p[find(b)] = find(a); // 这是将b插入到a的集合（总弄反了!!!）
        }
        else if(op == "Q1"){
            scanf("%d%d", &a, &b);
            if(find(a) == find(b))
                cout << "Yes" << endl;
            else
                cout << "No" << endl;
        }
        else{
            scanf("%d", &a);
            cout << s[find(a)] << endl;
        }
    }

    return 0;
}