题目背景 现代的人对于本家族血统越来越感兴趣。
题目描述 给出充足的父子关系，请你编写程序找到某个人的最早的祖先。
输入格式 输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系中父亲只有一行，儿子可能有若干行，用 #name 的形式描写一组父子关系中的父亲的名字，用 +name 的形式描写一组父子关系中的儿子的名字；接下来用 ?name 的形式表示要求该人的最早的祖先；最后用单独的一个 $ 表示文件结束。
输出格式 按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式为：本人的名字 ++ 一个空格 ++ 祖先的名字 ++ 回车。
输入输出样例
输入 #1 #George +Rodney #Arthur +Gareth +Walter #Gareth +Edward ?Edward ?Walter ?Rodney ?Arthur $
输出 #1 Edward Arthur Walter Arthur Rodney George Arthur Arthur
思路： 第一眼看是并查集，但是看这个输入就晕了，比较难处理，要么就是给每个人都标上记号，否则就只能用STL里的关联式容器map来做了（STL大法好！），把有关系的人记成：f[儿子]=父亲，这样就能记录他俩的关系，至于用不用并查集，我想都打了关联式容器了，我们就可以当成这是链表或者一棵树？当我们输入儿子要找祖先时，就一直向上找他的父亲，当儿子的父亲也有父亲是们就更新最大父亲（因为现在找的父亲不是祖先），如果找的这个父亲向上没有父亲了，证明他就是这个家族最大的父亲（也就是祖先）！
代码：
#include<map> #include<iostream> #include<cstring> using namespace std; map<string,string>f;//关联式容器map！ char s;//名字前的字符，判断关系 string x,a; int main(){ while(s!='$'){ cin>>s; if(s=='#') cin>>x,a=x;//如果是#号，证明是一个新父亲，并用a来记录新父亲 if(s=='+') cin>>x,f[x]=a;//如果是+号，证明是当前a父亲的儿子，f容器记录x和a的关系 if(s=='?'){//是？号说明要寻找此人的祖先 cin>>x; if(f[x].empty()){//如果此人本身就没有父亲，证明他就是自身的祖先 cout<<x<<" "<<x<<endl; continue; } a=f[x];//a来记录当前找到的最大祖先 while(!f[a].empty()) a=f[a];//如果父亲上面还有父亲，就更新最大父亲，用a记录 cout<<x<<" "<<a<<endl;//输出 } } return 0; }