3038: 【普及/提高-】【P2814】家谱
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
给出充足的父子关系，请你编写程序找到某个人的最早的祖先。
输入
输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系中父亲只有一行，儿子可能有若干行，用
#name 的形式描写一组父子关系中的父亲的名字，用 +name 的形式描写一组父子关系中的儿子的名字；接下来用 ?name 的形式表示要求该人的最早的祖先；最后用单独的一个 $ 表示文件结束。输出
按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式为：本人的名字 一个空格 祖先的名字 回车。
样例输入 复制
#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$样例输出 复制
Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur提示
规定每个人的名字都有且只有 个字符，而且首字母大写，且没有任意两个人的名字相同。最多可能有 组父子关系，总人数最多可能达到 人，家谱中的记载不超过 代。
#include<cstdio>
#include<iostream>
#include<map>
using namespace std;
map<string,string>p;
string find(string x)
{
if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
string s,s1;
int main()
{
char ch;
cin>>ch;
while(ch!='$')
{
cin>>s;
if(ch=='#')
{
s1=s;
if(p=="") p=s;
}
else if(ch=='+')
p=s1;
else
cout<<s<<' '<<find(s)<<endl;
cin>>ch;
}
return 0;
}