1346:【例4-7】亲戚(relation)

简介: 1346:【例4-7】亲戚(relation)

1346:【例4-7】亲戚(relation)

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

或许你并不知道,你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱,判断两个人是否是亲戚应该是可行的,但如果两个人的最近公共祖先与他们相隔好几代,使得家谱十分庞大,那么检验亲戚关系实非人力所能及。在这种情况下,最好的帮手就是计算机。为了将问题简化,你将得到一些亲戚关系的信息,如Marry和Tom是亲戚,Tom和Ben是亲戚,等等。从这些信息中,你可以推出Marry和Ben是亲戚。请写一个程序,对于我们的关于亲戚关系的提问,以最快的速度给出答案。

【输入】

输入由两部分组成。

第一部分以N,M开始。N为问题涉及的人的个数(1≤N≤20000)。这些人的编号为1,2,3,…, N。下面有M行(1≤M≤1000000),每行有两个数ai,bi,表示已知ai和bi是亲戚。

第二部分以Q开始。以下Q行有Q个询问(1≤ Q ≤1000000),每行为ci,di,表示询问ci和di是否为亲戚。

【输出】

对于每个询问ci,di,输出一行:若ci和di为亲戚,则输出“Yes”,否则输出“No”。

【输入样例】

10 7

2 4

5 7

1 3

8 9

1 2

5 6

2 3

3

3 4

7 10

8 9

【输出样例】

Yes

No

Yes

1. //示例代码  会超时
2. #include <iostream>
3. using namespace std;
4. int f[20005];
5. int find(int x){//查找x所在的集合
6.  if(f[x]==x) return x;//如果x自己就是一个集合的根节点,则返回x
7.  return f[x]=find(f[x]);//否则递归查找x的祖先节点
8. }
9. void unionn(int x,int y){//将x和y所在的集合合并
10.   f[find(x)]=find(y);
11. }
12. int main()
13. {
14.   int n,m,q,a,b;
15.   cin>>n>>m;
16.   for(int i=1;i<=n;i++) f[i]=i;//初始化每个人为一个单独的集合
17.   for(int i=1;i<=m;i++){ //处理已知亲戚关系
18.     cin>>a>>b;unionn(a,b);
19.   }
20.   cin>>q;
21.   for(int i=1;i<=q;i++){//查询每一对可能的亲戚
22.     cin>>a>>b;
23.     if(find(a)==find(b)) cout<<"Yes"<<endl;
24.     else cout<<"No"<<endl;
25.   }
26. return 0;
27. }

以上程序使用了并查集的数据结构。首先将每个人自己作为一个集合,并将已知的亲戚关系两个人所在的集合进行合并。然后对于每个询问,判断两个人是否所在同一个集合即可。在并查集上使用路径压缩优化之后,时间复杂度为O(mlogn)。以上代码会超时。

1. // 示例代码  AC
2. #include <iostream>
3. #include <stdio.h>
4. using namespace std;
5. int f[20005];
6. int find(int x){//查找x所在的集合
7.  if(f[x]==x) return x;//如果x自己就是一个集合的根节点,则返回x
8.  return f[x]=find(f[x]);//否则递归查找x的祖先节点
9. }
10. void unionn(int x,int y){
11.   f[x]=y;
12. }
13. int main()
14. {
15.   int n,m,q,a,b;
16.   scanf("%d %d",&n,&m);
17.   for(int i=1;i<=n;i++) f[i]=i;//初始化每个人为一个单独的集合 
18.   for(int i=1;i<=m;i++){ //处理已知亲戚关系
19.     scanf("%d %d",&a,&b);
20.     int x=find(a);
21.     int y=find(b);
22.     if(x!=y) unionn(x,y);
23.   }
24.   cin>>q;
25.   for(int i=1;i<=q;i++){//查询每一对可能的亲戚
26.     scanf("%d %d",&a,&b);
27.     if(find(a)==find(b)) puts("Yes");
28.     else puts("No");
29.   }
30. return 0;
31. }

这串代码必须用C语言的输入输出才能AC。


相关文章
|
分布式计算 Hadoop Java
【大数据开发技术】实验01-Hadoop安装部署
【大数据开发技术】实验01-Hadoop安装部署
477 0
|
6月前
|
SQL 分布式计算 IDE
如何在IDE中通过Spark操作Hive
通过以上方法和代码示例,你可以在IDE中成功通过Spark操作Hive,实现大规模数据处理和分析。确保理解每一步的实现细节,应用到实际项目中时能有效地处理各种复杂的数据场景。
342 28
|
机器学习/深度学习 自然语言处理 算法
7.1.3、使用飞桨实现基于LSTM的情感分析模型
该文章介绍了如何使用飞桨(PaddlePaddle)实现基于长短时记忆网络(LSTM)的情感分析模型,包括数据处理、网络定义、模型训练、评估和预测的详细步骤。
|
11月前
|
XML 开发工具 Android开发
FFmpeg开发笔记(五十六)使用Media3的Exoplayer播放网络视频
ExoPlayer最初是为了解决Android早期MediaPlayer控件对网络视频兼容性差的问题而推出的。现在,Android官方已将其升级并纳入Jetpack的Media3库,使其成为音视频操作的统一引擎。新版ExoPlayer支持多种协议,解决了设备和系统碎片化问题,可在整个Android生态中一致运行。通过修改`build.gradle`文件、布局文件及Activity代码,并添加必要的权限,即可集成并使用ExoPlayer进行网络视频播放。具体步骤包括引入依赖库、配置播放界面、编写播放逻辑以及添加互联网访问权限。
773 1
FFmpeg开发笔记(五十六)使用Media3的Exoplayer播放网络视频
|
敏捷开发 前端开发 测试技术
软件开发工作流【详解】(含公司产品研发流程图、大厂研发架构图、大厂研发流程图)
软件开发工作流【详解】(含公司产品研发流程图、大厂研发架构图、大厂研发流程图)
5989 1
|
存储 缓存 API
Flask 框架在大型 Web 应用中的使用与挑战
【5月更文挑战第18天】Flask框架适用于快速开发轻量级Web应用,但用于大型应用时需应对性能、代码管理和团队协作的挑战。通过集成扩展处理复杂需求,使用蓝图组织代码,以及引入缓存优化性能,结合明确的代码规范和开发流程,可有效应对挑战,构建高效稳定的应用。
218 5
|
机器学习/深度学习 人工智能 前端开发
探索未来:2024年前端技术趋势解读
探索未来:2024年前端技术趋势解读
540 4
|
Java
Java接口中可以定义哪些方法?
【4月更文挑战第13天】
841 0
Java接口中可以定义哪些方法?
|
算法 Java 调度
Semaphore实现原理全面解析
Semaphore(信号量)是一个同步工具类,通过Semaphore可以控制同时访问共享资源的线程个数。
|
Java 数据库 Android开发
基于SpringBoot校园外卖服务系统设计与实现
基于SpringBoot校园外卖服务系统设计与实现