博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
一个找亲戚游戏,引发了一场算法的学习——并查集
阅读量:5827 次
发布时间:2019-06-18

本文共 708 字,大约阅读时间需要 2 分钟。

题目描述:

           若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。

           规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。

           如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。

输入:

          第一行:三个整数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个询问的答案为“具有”或“不具有”亲戚关系。

讲解:   这是一场简单的找  father 的游戏,如果两个小伙伴,有一个共同的爹,他们两个就有亲戚关系了;也反映出了,并查集在解决问题方面的巨大潜能;

1 #include
2 #include
3 #include
4 #include
5 using namespace std; 6 int father[50002],a,b,m,n,p; 7 int find(int x){ 8 if (father[x]!=x){ //如果自己还是自己的爹,直接返回,否则找到最终的父亲,当成自己的爹 9 //cout<<"儿子 "<
<
"<
<

 

转载地址:http://viadx.baihongyu.com/

你可能感兴趣的文章
通过Roslyn构建自己的C#脚本(更新版)(转)
查看>>
红黑树
查看>>
UIImagePickerController拍照与摄像
查看>>
python调用windows api
查看>>
第四章 mybatis批量insert
查看>>
Java并发框架——什么是AQS框架
查看>>
【数据库】
查看>>
Win配置Apache+mod_wsgi+django环境+域名
查看>>
linux清除文件内容
查看>>
WindowManager.LayoutParams 详解
查看>>
find的命令的使用和文件名的后缀
查看>>
Android的Aidl安装方法
查看>>
Linux中rc的含义
查看>>
曾鸣:区块链的春天还没有到来| 阿里内部干货
查看>>
如何通过Dataworks禁止MaxCompute 子账号跨Project访问
查看>>
js之无缝滚动
查看>>
Django 多表联合查询
查看>>
logging模块学习:basicConfig配置文件
查看>>
Golang 使用 Beego 与 Mgo 开发的示例程序
查看>>
+++++++子域授权与编译安装(一)
查看>>