[并查集] 连通块中点的数量(模板+维护集合元素个数)

1. 并查集+动态维护集合个数

可以在并查集的基本操作中维护一些额外信息，如维护集合中的点的个数。

新添加一个数组 s[N] 只维护一个集合的树根节点位置的信息，在 s[find(x)] 存储这个集合的元素个数。

注意：

• 初始化数组 s 为 1，意味着集合中只有它自身一个元素
• 合并两个集合的时候，更新 s 数组，就是简单的加和
• 当两个元素已经在一个集合中的时候，不能再对 s 进行操作，这相当于集合元素个数的翻倍。

代码：

#include <iostream>

using namespace std;

const int N = 1e5+5;

int n, m;
int p[N], 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;
    
    while (m --) {
        char op[2];
        int a, b;
        cin >> op;
        if (op[0] == 'C') {
            cin >> a >> b;
            // 如果a,b在同一个集合里，则直接continue，不用再累加集合元素了
            if (find(a) == find(b)) continue;   
            s[find(b)] += s[find(a)];
            p[find(a)] = find(b);
        } else if (op[1] == '1') {
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        } else {
            cin >> a;
            cout << s[find(a)] << endl;
            
        }
    }
}