837.连通块中点的数量

tip

原题链接：https://www.acwing.com/problem/content/837/

思路

将连通块转换成集合来存储，一个连通块就是一个集合。

连接两条边等价于两个集合进行合并。

查询两个点是否在同一个连通块等价于查找两个点是否在同一个集合。

故使用并查集模板。

因为还要求解其连通块当中点的数量，故需要在并查集的过程中再维护一个数量的数组，与并查集同步进行。

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

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 --) {
        string ops;
        int a, b;
        
        cin >> ops;
        if (ops == "C") {
            cin >> a >> b;
            a = find(a), b = find(b);
            if (a != b) {
                p[a] = b;
                s[b] += s[a];
            }
        } else if (ops == "Q1") {
            cin >> a >> b;
            if (find(a) == find(b)) cout << "Yes" << endl;
            else cout << "No" << endl;
        } else if (ops == "Q2") {
            cin >> a;
            cout << s[find(a)] << endl;
        }
    }
    
    return 0;
}