郑州网站设计 郑州网站开发,重庆造价协会官网,seo技能培训,网站表单及商品列表详情模板文章目录 837. 连通块中点的数量题目描述维护size的并查集 837. 连通块中点的数量
题目描述
给定一个包含 n 个点#xff08;编号为 1#xff5e;n#xff09;的无向图#xff0c;初始时图中没有边。
现在要进行 m 个操作#xff0c;操作共有三种#xff1a;
C a b编号为 1n的无向图初始时图中没有边。
现在要进行 m 个操作操作共有三种
C a b在点 a 和点 b 之间连一条边a 和 b 可能相等Q1 a b询问点 a 和点 b 是否在同一个连通块中a 和 b 可能相等Q2 a询问点 a 所在连通块中点的数量
输入格式 第一行输入整数 n 和 m。
接下来 m 行每行包含一个操作指令指令为 C a bQ1 a b 或 Q2 a 中的一种。
输出格式
对于每个询问指令 Q1 a b如果 a 和 b 在同一个连通块中则输出 Yes否则输出 No。
对于每个询问指令 Q2 a输出一个整数表示点 a 所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤105
输入样例
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5输出样例
Yes
2
3维护size的并查集
#includebits/stdc.h // 包含大多数标准库
using namespace std;const int z1e510; // 定义常数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操作输出给定节点所在连通块的大小。
这个程序对应了题目描述中的需求它可以有效地处理大量的连通性查询和连通块大小查询。
