软件网站开发公司,商品关键词举例,定制柜需要多少钱,tp5网站开发模板下载一、链接
837. 连通块中点的数量
二、题目
给定一个包含 nn 个点#xff08;编号为 1∼n1∼n#xff09;的无向图#xff0c;初始时图中没有边。
现在要进行 mm 个操作#xff0c;操作共有三种#xff1a;
C a b#xff0c;在点 aa 和点 bb 之间连一条边#xff0c…一、链接
837. 连通块中点的数量
二、题目
给定一个包含 nn 个点编号为 1∼n1∼n的无向图初始时图中没有边。
现在要进行 mm 个操作操作共有三种
C a b在点 aa 和点 bb 之间连一条边aa 和 bb 可能相等Q1 a b询问点 aa 和点 bb 是否在同一个连通块中aa 和 bb 可能相等Q2 a询问点 aa 所在连通块中点的数量
输入格式
第一行输入整数 nn 和 mm。
接下来 mm 行每行包含一个操作指令指令为 C a bQ1 a b 或 Q2 a 中的一种。
输出格式
对于每个询问指令 Q1 a b如果 aa 和 bb 在同一个连通块中则输出 Yes否则输出 No。
对于每个询问指令 Q2 a输出一个整数表示点 aa 所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5输出样例
Yes
2
3
三、题意
如果两个点之间是连接的就表示这两个点构成了一个连通块连通块是原图的子图子图之外没有点和子图内部的点有联系也就是说子图之外只要有一个点和子图有联系就会形成一个新的子图。
我们需要进行多次操作C是合并两个元素Q1是查询是否是同一个集合Q2是查询有多少个元素属于这个集合
四、代码
#includeiostreamusing namespace std;const int N1e510;int p[N],si[N];int find(int x)
{if(p[x]!x){p[x]find(p[x]);}return p[x];
}int main()
{int n,m;scanf(%d%d,n,m);for(int i1;in;i){p[i]i;si[i]1;}while(m--){char op[2];int a,b;scanf(%s,op);if(op[0]C){scanf(%d%d,a,b);afind(a),bfind(b);if(ab){continue;}p[a]b;si[b]si[a];}else if(op[1]1){scanf(%d%d,a,b);if(find(a)find(b)){printf(Yes\n);}else{printf(No\n);}}else{scanf(%d,a);printf(%d\n,si[find(a)]);}}return 0;
}
五、总结
1.并查集的简单应用做出这道题目最好不要在脑子里面模拟初学或者不熟悉题型最好还是在纸上详细模拟实现寻找他应该使用什么算法然后把算法模板应用上去比如说这道题目就是处理两个元素最开始两个元素是孤立的后面把两个元素合并到一个集合连通块判断两个元素是不是连通块其实就是判断两个元素是不是属于同一个集合连通块大小的话直接把大小存在根节点维护根节点的大小即可。
2.并查集的模板并查集模板-两个操作合并集合和查询两个元素是否属于同一个集合
3.什么是连通块连通块概念
4.continue的作用continue
5.continue在这里的作用a和b两个元素相等的话就不把两个元素的根节点的size更新因为更新的话就会变成原来的两倍但是根据实际情况在这里是不需要更新的注意这里如果两个元素属于同一个连通块的话也是需要直接跳出后续的合并步骤的不仅仅是两个元素相等操作完之后再出现操作过的数字还是不再需要处理
6.把a和b的根节点先取出来a的根节点更新之后会和b的根节点重合那时再去维护size将会发生错误所以要么把根节点取出来要么先更新size再更新根节点
7.熟练应用熟能生巧
六、精美图片
