洛谷 P1551 亲戚【并查集】
发布日期:2021-07-01 02:47:48
浏览次数:3
分类:技术文章
本文共 1264 字,大约阅读时间需要 4 分钟。
题目背景
若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。题目描述
规定:x
和 y
是亲戚,y
和 z
是亲戚,那么 x
和 z
也是亲戚。如果 x,y
是亲戚,那么 x
的亲戚都是 y
的亲戚,y
的亲戚也都是 x
的亲戚。 输入格式
第一行:三个整数 n , m , p n,m,p n,m,p,(n<=5000,m<=5000,p<=5000
),分别表示有 n
个人,m
个亲戚关系,询问 p
对亲戚关系。 以下 m
行:每行两个数 Mi,Mj,1<=Mi,Mj<=N
,表示 Mi
和 Mj
具有亲戚关系。 接下来 p
行:每行两个数 Pi,Pj
,询问 Pi
和 Pj
是否具有亲戚关系。 输出格式
P
行,每行一个 ’Yes
’或 ’No
’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。 输入输出样例
输入 #16 5 31 21 53 45 21 31 42 35 6
输出 #1
YesYesNo
说明/提示:非常简单的并查集入门题哦!!!
题目:判断两个人是否是亲戚关系。
思路:套并查集的模板。很简单。代码:
#includeusing namespace std;const int maxn = 5100;int n, m, p, mi, mj, pi, pj;int father[maxn] = { 0};void Init() { for (int i = 0; i < maxn; ++i) father[i] = -1;}int Find(int x) { //找到集合的根 if (father[x] < 0) return x; return father[x] = Find(father[x]);}void Union(int r1, int r2) { if (father[r1] < father[r2]) { //按大小合并 father[r1] += father[r2]; father[r2] = r1; } else { father[r2] += father[r1]; father[r1] = r2; }}int main() { cin >> n >> m >> p; Init(); for (int i = 0; i < m; ++i) { cin >> mi >> mj; int r1 = Find(mi), r2 = Find(mj); if (r1 != r2) Union(r1, r2); } for (int i = 0; i < p; ++i) { cin >> pi >> pj; if (Find(pi) == Find(pj)) cout << "Yes\n"; else cout << "No\n"; } return 0;}
转载地址:https://memcpy0.blog.csdn.net/article/details/106655074 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月11日 20时01分07秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Java--流重点总结初稿
2019-05-01
ImageView scaleType
2019-05-01
字符串的排序
2019-05-01
内存分配(mallloc,calloc,realloc,new)
2019-05-01
使用 Minidumps 和 Visual Studio .NET 进行崩溃后调试
2019-05-01
struts返回xml数据例子
2019-05-01
内存对齐详解
2019-05-01
秋招总结(一)-C++归纳
2019-05-01
秋招总结(三)-操作系统归纳
2019-05-01
带缓冲I/O 和不带缓冲I/O的区别与联系
2019-05-01
LINUX CP命令详解
2019-05-01
source insight快捷键及使用技巧
2019-05-01
映 射 ALT 键
2019-05-01
vim使用快捷键F4生成文件头注释、F5生成main函数模板、F6生成.h文件框架模板
2019-05-01
OV5620的视频驱动
2019-05-01
C++中两个类交叉定义或递归定义的解决办法
2019-05-01
ECharts is not Loaded解决方案
2019-05-01
echarts切换tab时,第一个图表显示,第二个图表不显示的解决办法
2019-05-01