acwing-837. 连通块中点的数量

给定一个包含 n 个点（编号为 1～n）的无向图，初始时图中没有边。

现在要进行 m 个操作，操作共有三种：

1. C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
2. Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
3. Q2 a，询问点 a 所在连通块中点的数量；

输入格式

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量

每个结果占一行。

数据范围

1≤n,m≤10⁵

输入样例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：

Yes
2
3

方法一：

并查集模板题2，根节点记录集合大小的相反数

#include 

using namespace std;

const int N = 100010;
int n, m;
int p[N];

int find(int x) {
    if (p[x] > 0) {
        p[x] = find(p[x]);
        return p[x];
    }
    else return x;
}

void merge(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra != rb) {
        // 小树合并到大树
        if (p[ra] < p[rb]) {
            p[ra] += p[rb];
            p[rb] = ra;
        } else {
            p[rb] += p[ra];
            p[ra] = rb;
        }
    }
}

int main() {
    int a, b;
    char op[3];
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; ++i) p[i] = -1;

    while (m--) {
        scanf("%s", op);
        if (op[0] == 'C') {
            scanf("%d%d", &a, &b);
            merge(a, b);
        }
        else if (op[1] == '1') {
            scanf("%d%d", &a, &b);
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        } else {
            scanf("%d", &a);
            printf("%d\n", -p[find(a)]);
        }
    }
}