不會并查集的話請將此文與我以前寫的并查集一同食用选调。
原題來自洛谷
原題
文字稿在此：
題目背景
現(xiàn)代的人對于本家族血統(tǒng)越來越感興趣夹供。
題目描述
給出充足的父子關系，請你編寫程序找到某個人的最早的祖先仁堪。
輸入輸出格式
輸入格式：
輸入由多行組成哮洽，首先是一系列有關父子關系的描述，其中每一組父子關系中父親只有一行弦聂，兒子可能有若干行鸟辅，用#name的形式描寫一組父子關系中的父親的名字，用+name的形式描寫一組父子關系中的兒子的名字横浑；接下來用?name的形式表示要求該人的最早的祖先剔桨；最后用單獨的一個$表示文件結束。
輸出格式：
按照輸入文件的要求順序徙融，求出每一個要找祖先的人的祖先洒缀，格式：本人的名字+一個空格+祖先的名字+回車。
輸入輸出樣例
輸入樣例#1：
#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$
輸出樣例#1：
Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur
說明
規(guī)定每個人的名字都有且只有6個字符欺冀，而且首字母大寫树绩，且沒有任意兩個人的名字相同。最多可能有1000組父子關系隐轩，總人數(shù)最多可能達到50000人饺饭，家譜中的記載不超過30代。
map
map是STL中的一種數(shù)據(jù)結構职车，你可以理解為它是一個下表不一定 為整形的數(shù)組（也就是說瘫俊，下表可以為字符鹊杖、字符串。扛芽。骂蓖。）
map類型的聲明
大體模式式是
map<下標類型，數(shù)組每一個元素的類型> 數(shù)組名;
比如說我要一個下表是字符串川尖，每一個元素的類型也是字符串登下，名字叫a的數(shù)組，我可以這樣寫
map<string,string> a;
回到題目
會了map叮喳，相信你應該也有點思路了吧被芳？這是 建立在并查集基礎上的，不會并查集的話馍悟，可以看看我以前寫的并查集畔濒。
有了map我們就可以使用 真正意義上的字符串數(shù)組來編程了！８畴篓冲！
函數(shù)
這里面的getfather函數(shù) 變異了，他成了這樣
string getfather(string x)//找x的根結點
{//這其實是一個遞歸函數(shù)
if(father[x]!=x)
{
return getfather(father[x]);//它會一級一級找上去（先找到它爸爸宠哄，在找到它爸爸的爸爸，再找到它爸爸的爸爸的爸爸嗤攻。毛嫉。。妇菱。承粤。）
}
else
{
return father[x];//邊界條件，如果x的根結點就是x（也就是說它沒有更上邊的祖宗了）
}
}
相較以前的getfather闯团，首先函數(shù)的類型成了string辛臊，而且x的類型也是string。但是作用和以前是一樣的房交。
讀入
這題的讀入很特殊彻舰，因為這道題要邊讀入邊處理邊輸出
char c;//就是名字 前面那個字符
string s,fat;//s是名字，fat是是用來暫存先提及的父親的名字的
這題我用了這幾個變量候味。
核心代碼如下
map<string,string> father;//用來存儲某一點的根結點
cin>>c;//讀入c
while(c!='$')//只要c不是$就會執(zhí)行
{
cin>>s;//讀入名字
if(c=='#')//假如讀到了父親 的名字
{
fat=s;//fat暫存父親的名字刃唤，因為過一會兒s的值會變
if(father[s]=="") father[s]=s;//如果father[s]的值為空，也就是說s就是自己的根結點（找到底了）
}
if(c=='+')//如果s是表示兒子
{
father[s]=fat;//s的根結點就成了fat（上面說的fat這是就派上了用場）
}
if(c=='?')//查集
{
cout<<s<<' '<<getfather(father[s])/*輸出father[s]的根結點*/<<endl;
}
cin>>c;//讀入c白群，開始新一輪的循環(huán)
}
完整程序如下
#include<map>
#include<iostream>
using namespace std;
map<string,string> father;
string getfather(string x)
{
if(father[x]!=x)
{
return getfather(father[x]);
}
else
{
return father[x];
}
}
int main()
{
char c;
string s,fat;
cin>>c;
while(c!='$')
{
cin>>s;
if(c=='#')
{
fat=s;
if(father[s]=="") father[s]=s;
}
if(c=='+')
{
father[s]=fat;
}
if(c=='?')
{
cout<<s<<' '<<getfather(father[s])<<endl;
}
cin>>c;
}
return 0;
}
總結
這題其實和并查集的模版的差異并不大尚胞，只是涉及到STL中的數(shù)據(jù)結構map的使用。所以對于提高+的評價感覺是過了點帜慢，但要是不會map的話可能真的是這個難度了笼裳。
如果字符串功底夠好唯卖，也可以 考慮用字符串/字符 數(shù)組來實現(xiàn)（我字符串功底不好。躬柬。）
tks耐床。
