【題目描述】

現(xiàn)代的人對于本家族血統(tǒng)越來越感興趣，現(xiàn)在給出充足的父子關(guān)系，請你編寫程序找到某個(gè)人的最早的祖先。

【輸入】

由多行組成，首先是一系列有關(guān)父子關(guān)系的描述，其中每一組父子關(guān)系由二行組成，用#name的形式描寫一組父子關(guān)系中的父親的名字，用+name的形式描寫一組父子關(guān)系中的兒子的名字；接下來用?name的形式表示要求該人的最早的祖先；最后用單獨(dú)的一個(gè)$表示文件結(jié)束。規(guī)定每個(gè)人的名字都有且只有6個(gè)字符，而且首字母大寫，且沒有任意兩個(gè)人的名字相同。最多可能有1000組父子關(guān)系，總?cè)藬?shù)最多可能達(dá)到50000人，家譜中的記載不超過30代。

【輸出】

按照輸入的要求順序，求出每一個(gè)要找祖先的人的祖先，格式：本人的名字+一個(gè)空格+祖先的名字+回車。

【輸入樣例】

#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$

【輸出樣例】

Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<set> #include<map> #include<stack> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 10001 #define MOD 123 #define E 1e-6 using namespace std; map <string,string> father; string Find(string x) {if(father[x]==x)return x;return father[x]=Find(father[x]); } int main() {string str;string temp1,temp2,temp3;while(cin>>str&&str!="$"){if(str[0]=='#'){temp1=str.substr(1,str.size()-1);if(father[temp1]=="")father[temp1]=temp1;}else if(str[0]=='+'){temp2=str.substr(1,str.size()-1);Find(temp1);father[temp2]=father[temp1];}else if(str[0]=='?'){temp3=str.substr(1,str.size()-1);Find(temp3);cout<<temp3<<" "<<father[temp3]<<endl;}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的家谱（信息学奥赛一本通-T1388）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。