837. 连通块中点的数量(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

维护size的并查集

#include<bits/stdc++.h> // 包含大多数标准库
using namespace std;const int z=1e5+10; // 定义常数z为最大点数加10，用于数组大小int fa[z], size[z]; // fa数组存储每个点的父节点，size数组存储每个连通块的大小// 并查集的查找函数，用于查找元素i的根节点，并执行路径压缩
int find(int i) {if(fa[i] != i) fa[i] = find(fa[i]); // 路径压缩，递归地将fa[i]更新为根节点return fa[i]; // 返回根节点
}// 主函数
int main() {int n, m; // n表示点的数量，m表示操作的数量cin >> n >> m; // 输入点的数量和操作的数量// 初始化并查集for (int i = 1; i <= n; i++) {fa[i] = i; // 每个点的父节点初始化为自己size[i] = 1; // 每个点所在连通块的大小初始化为1}// 循环处理m个操作while (m--) {string s; // 存储操作类型cin >> s; // 输入操作类型// 根据不同的操作类型进行操作if(s == "C") { // 连接操作int a, b;cin >> a >> b; // 输入要连接的两个点的编号if(find(a) == find(b)) continue; // 如果已经在同一个连通块中，无需操作// 否则，合并两个连通块size[find(b)] += size[find(a)]; // 更新根节点的连通块大小fa[find(a)] = find(b); // 将一个点的根节点连接到另一个点的根节点} else if(s == "Q1") { // 查询操作1，询问两个点是否连通int a, b;cin >> a >> b; // 输入要查询的两个点的编号if(find(a) == find(b)) cout << "Yes" << endl; // 如果根节点相同，输出Yeselse cout << "No" << endl; // 否则，输出No} else { // 查询操作2，询问连通块的大小int a;cin >> a; // 输入要查询的点的编号cout << size[find(a)] << endl; // 输出该点所在连通块的大小}}return 0;
}

在这段代码中，主要用到了两个全局数组fa和size。fa数组用来表示每个节点的父节点，初始化时每个节点都是自己的父节点。size数组用来表示以当前节点为根节点的连通块的大小，初始化为1。每次合并连通块时，会更新这两个数组的信息。

find函数是并查集的核心，用于查找节点的根节点，并在这个过程中进行路径压缩。

在main函数中，代码首先接收输入的节点数和操作数，然后通过循环处理每一条操作指令。指令分为三种类型，分别对应代码中的三个分支。

• C操作将两个节点连接在一起，如果它们不在同一个连通块中，会合并它们所在的连通块，并更新连通块大小。
• Q1操作判断两个节点是否在同一个连通块中，输出结果。
• Q2操作输出给定节点所在连通块的大小。

这个程序对应了题目描述中的需求，它可以有效地处理大量的连通性查询和连通块大小查询。