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. }