题解：AcWing 837 连通块中点的数量

【题目来源】

AcWing：837. 连通块中点的数量 - AcWing题库

【题目描述】

给定一个包含 \(n\) 个点（编号为 \(1\sim 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\) 所在连通块中点的数量

每个结果占一行。

【输入样例】

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

【输出样例】

Yes
2
3

【算法标签】

《AcWing 837 连通块中点数量》 #并查集#

【代码详解】

#include <bits/stdc++.h>
using namespace std;const int N = 100010;  // 定义最大节点数int n, m;        // n: 节点数量, m: 操作次数
int p[N];        // 并查集父节点数组
int siz[N];      // 记录每个集合的大小// 查找x的根节点（带路径压缩优化）
int find(int x)
{if (p[x] != x)          // 如果当前节点不是根节点p[x] = find(p[x]);  // 路径压缩：将父节点设为根节点return p[x];            // 返回根节点
}int main()
{scanf("%d%d", &n, &m);  // 输入节点数和操作数// 初始化并查集for (int i = 1; i <= n; i++){p[i] = i;      // 每个节点自成一个集合siz[i] = 1;    // 初始集合大小为1}while (m--)  // 处理每个操作{char op[5];  // 操作类型int a, b;    // 操作参数scanf("%s", op);if (op[0] == 'C') {// 合并操作：将a所在集合合并到b所在集合scanf("%d%d", &a, &b);if (find(a) == find(b)) continue;  // 已在同一集合则跳过siz[find(b)] += siz[find(a)];  // 合并集合大小p[find(a)] = find(b);          // 将a的根节点指向b的根节点}else if (op[1] == '1') {// 查询操作：判断a和b是否在同一集合scanf("%d%d", &a, &b);if (find(a) == find(b))puts("Yes");elseputs("No");}else {// 查询操作：返回a所在集合的大小scanf("%d", &a);printf("%d\n", siz[find(a)]);}}return 0;
}

【运行结果】

5 5
C 1 2
Q1 1 2
Yes
Q2 1
2
C 2 5
Q2 5
3
gu