1388:家谱(gen)

简介: 1388:家谱(gen)

1388:家谱(gen)

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

【题目描述】

现代的人对于本家族血统越来越感兴趣,现在给出充足的父子关系,请你编写程序找到某个人的最早的祖先。

【输入】

由多行组成,首先是一系列有关父子关系的描述,其中每一组父子关系由二行组成,用#name的形式描写一组父子关系中的父亲的名字,用+name的形式描写一组父子关系中的儿子的名字;接下来用?name的形式表示要求该人的最早的祖先;最后用单独的一个$表示文件结束。规定每个人的名字都有且只有6个字符,而且首字母大写,且没有任意两个人的名字相同。最多可能有1000组父子关系,总人数最多可能达到50000人,家谱中的记载不超过30代。

【输出】

按照输入的要求顺序,求出每一个要找祖先的人的祖先,格式:本人的名字+一个空格+祖先的名字+回车。

【输入样例】

#George

+Rodney

#Arthur

+Gareth

+Walter

#Gareth

+Edward

?Edward

?Walter

?Rodney

?Arthur

$

【输出样例】

Edward Arthur

Walter Arthur

Rodney George

Arthur Arthur

1. //示例代码
2. #include <iostream>
3. #include <cstdio>
4. #include <string>
5. using namespace std;
6. const int N=50005;
7. int f[N],lf;         // f为并查集,lf为当前name数组中的人数
8. string name[N],x,y;  // name数组存放每个人的名字,x和y为临时变量
9. char c;              // c为当前输入的命令类型
10. 
11. // find函数用于在name数组中查找指定名字对应的编号,如果该名字不存在则将其加入数组中并返回新的编号
12. int find(string s){
13.   for(int i=1;i<=lf;i++)
14.     if(s==name[i]) return i;
15.   name[++lf]=s;
16.   return lf;
17. }
18. 
19. // fa函数为并查集查找函数,用于查找x号元素所在集合的根节点,并进行路径压缩优化
20. int fa(int x){
21.   if(f[x]==x) return f[x];
22.   return f[x]=fa(f[x]);
23. }
24. 
25. int main(){
26. for(int i=1;i<=50000;i++) f[i]=i;  // 初始化并查集
27. while(cin>>c){
28. if(c=='$') break;
29. switch(c){
30. case '#':
31.                 cin>>x;                  // 输入父亲的名字,或者新建一个人的名字并加入name数组
32. break;
33. case '+':
34.                 cin>>y;                  // 输入儿子的名字
35. if(x!=y)f[fa(find(y))]=fa(find(x));   // 如果父亲和儿子不是同一个人,则将它们的集合合并
36. break;
37. case '?':
38.                 cin>>y;                  // 输入要查询祖先的人的名字
39.                 cout<<y<<" "<<name[fa(find(y))]<<endl;   // 输出该人的名字和最早的祖先的名字
40. break;
41.         }
42.     }
43. return 0;
44. }


目录
打赏
0
0
0
0
3
分享
相关文章
【软件设计师备考 专题 】设计数据模型:ER模型和数据模型
【软件设计师备考 专题 】设计数据模型:ER模型和数据模型
425 0
用Qemu模拟vexpress-a9 (三)--- 实现用u-boot引导Linux内核
用Qemu模拟vexpress-a9 (三)--- 实现用u-boot引导Linux内核
一分钟解决Excel多人协作的版本混乱问题
多人协同编辑Excel彻底解决了传统多人编辑时的版本混乱问题。通过云端实时同步,团队成员可以同时更新同一表格,避免了邮件传递和手动合并的繁琐。实时协作不仅提升了效率,还防止了版本冲突。Excel的“更改历史记录”功能支持查看和回滚操作,确保错误可追溯。
基于python豆瓣电影评论的情感分析和聚类分析,聚类分析有手肘法进行检验,情感分析用snownlp
本文介绍了一个基于Python的情感分析和聚类分析项目,使用snownlp库对豆瓣电影评论进行情感分析,并采用手肘法辅助K-means算法进行聚类分析,以探索评论中的不同主题和情感集群。
291 5
基于python豆瓣电影评论的情感分析和聚类分析,聚类分析有手肘法进行检验,情感分析用snownlp
大文件上传实现方式比较
大文件上传实现方式比较
220 5
|
12月前
|
zookeeper 集群环境搭建及集群选举及数据同步机制
zookeeper 集群环境搭建及集群选举及数据同步机制
321 2
大师学SwiftUI第18章Part2 - 存储图片和自定义相机
在前面的示例中,我们在屏幕上展示了图片,但也可以将其存储到文件或数据库中。另外有时使用相机将照片存储到设备的相册薄里会很有用,这样可供其它应用访问。UIKit框架提供了如下两个保存图片和视频的函数。 •
540 0
探索Linux设备树:硬件描述与驱动程序的桥梁
探索Linux设备树:硬件描述与驱动程序的桥梁
1015 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问