B - 最近公共祖先
HihoCoder - 1062
描述
小Ho最近發(fā)現(xiàn)了一個(gè)神奇的網(wǎng)站！雖然還不夠像58同城那樣神奇，但這個(gè)網(wǎng)站仍然讓小Ho樂在其中，但這是為什么呢？
“為什么呢壁畸？”小Hi如是問道，在他的觀察中小Ho已經(jīng)沉迷這個(gè)網(wǎng)站一周之久了茅茂，甚至連他心愛的樹玩具都棄置一邊捏萍。
“嘿嘿，小Hi空闲，你快過來看令杈！”小Ho招呼道。
“你看碴倾，在這個(gè)對(duì)話框里輸入我的名字逗噩，在另一個(gè)對(duì)話框里，輸入你的名字跌榔，再點(diǎn)這個(gè)查詢按鈕异雁，就可以查出來……什么！我們居然有同一個(gè)祖祖祖祖祖爺爺僧须？”
“誒纲刀，真是誒……這個(gè)網(wǎng)站有點(diǎn)厲害啊〉Ｆ剑”小Hi不由感嘆道示绊。
“是啊锭部，這是什么算法啊，這么厲害面褐！”小Ho也附和道拌禾。
“別2，我說的是他能弄到這些數(shù)據(jù)很厲害盆耽，而人類的繁殖樹這種層數(shù)比較淺的樹對(duì)這類算法的要求可是簡單的不得了蹋砚，你都能寫出來呢扼菠！”小Hi道摄杂。
“啊循榆？我也能寫出來析恢？可是……該從哪開始呢？”小Ho困惑了秧饮。
小Ho要面臨的問題是這樣的映挂，假設(shè)現(xiàn)在他知道了N個(gè)人的信息——他們的父親是誰，他需要對(duì)于小Hi的每一次提問——兩個(gè)人的名字盗尸，告訴小Hi這兩個(gè)人的是否存在同一個(gè)祖先柑船，如果存在，那么他們的所有共同祖先中輩分最低的一個(gè)是誰泼各？
提示：不著急鞍时，慢慢來，另外我有一個(gè)問題：挖掘機(jī)技術(shù)哪家強(qiáng)扣蜻？逆巍！
× Close 提示：不著急，慢慢來莽使，另外我有一個(gè)問題：挖掘機(jī)技術(shù)哪家強(qiáng)锐极？！
小Hi道：“這個(gè)問題也應(yīng)該是樹結(jié)構(gòu)許許多多問題中頗為經(jīng)典的一個(gè)了芳肌，如果就簡單的將父子關(guān)系視作樹結(jié)構(gòu)中的父子結(jié)點(diǎn)關(guān)系的話灵再，這個(gè)問題其實(shí)就是在問樹中兩個(gè)結(jié)點(diǎn)層數(shù)最高的公共祖先——也就是所謂的最近公共祖先，而這個(gè)問題有非常多的解決方法亿笤，分別適合于不同的場(chǎng)景翎迁，像在線算法離線算法什么的現(xiàn)在說給你聽你也不一定能夠很快理解≡鹑拢”
“但是……你不是說我能夠?qū)懗鰜淼拿丛蓿俊毙o納悶了。
“所以說我們慢慢來不要急罕拂，先教你個(gè)最簡單的法子揍异∪桑”小Hi如是說道。
“最簡單的法子……如果數(shù)據(jù)量不大的話衷掷，我完全可以直接將這兩個(gè)人的祖先全部找出來辱姨，然后取它們的交集，然后再找到其中輩分最低的一個(gè)不就行了戚嗅∮晏危”小Ho思考了會(huì)這般說道。
小Hi點(diǎn)了點(diǎn)頭道：“差不多就是這樣懦胞！當(dāng)然你也先將一個(gè)人的祖先全都標(biāo)記出來替久，然后順著另一個(gè)的父親一直向上找，直到找到第一個(gè)被標(biāo)記過的結(jié)點(diǎn)躏尉，便是它們的最近公共祖先結(jié)點(diǎn)了蚯根。”
“原來這么簡單胀糜！”小Ho笑道：“那我先去寫著了颅拦。”
輸入
每個(gè)測(cè)試點(diǎn)（輸入文件）有且僅有一組測(cè)試數(shù)據(jù)教藻。
每組測(cè)試數(shù)據(jù)的第1行為一個(gè)整數(shù)N距帅，意義如前文所述。
每組測(cè)試數(shù)據(jù)的第2~N+1行括堤，每行分別描述一對(duì)父子關(guān)系碌秸，其中第i+1行為兩個(gè)由大小寫字母組成的字符串Father_i, Son_i，分別表示父親的名字和兒子的名字痊臭。
每組測(cè)試數(shù)據(jù)的第N+2行為一個(gè)整數(shù)M哮肚，表示小Hi總共詢問的次數(shù)。
每組測(cè)試數(shù)據(jù)的第N+3~N+M+2行广匙，每行分別描述一個(gè)詢問允趟，其中第N+i+2行為兩個(gè)由大小寫字母組成的字符串Name1_i, Name2_i，分別表示小Hi詢問中的兩個(gè)名字鸦致。
對(duì)于100%的數(shù)據(jù)潮剪，滿足N<=102，M<=102, 且數(shù)據(jù)中所有涉及的人物中不存在兩個(gè)名字相同的人（即姓名唯一的確定了一個(gè)人）分唾。
輸出
對(duì)于每組測(cè)試數(shù)據(jù)抗碰，對(duì)于每個(gè)小Hi的詢問，輸出一行绽乔，表示查詢的結(jié)果：如果根據(jù)已知信息弧蝇，可以判定詢問中的兩個(gè)人存在共同的祖先，則輸出他們的所有共同祖先中輩分最低的一個(gè)人的名字，否則輸出-1看疗。
Sample Input
11
JiaYan JiaDaihua
JiaDaihua JiaFu
JiaDaihua JiaJing
JiaJing JiaZhen
JiaZhen JiaRong
JiaYuan JiaDaishan
JiaDaishan JiaShe
JiaDaishan JiaZheng
JiaShe JiaLian
JiaZheng JiaZhu
JiaZheng JiaBaoyu
3
JiaBaoyu JiaLian
JiaBaoyu JiaZheng
JiaBaoyu LinDaiyu
Sample Output
JiaDaishan
JiaZheng
-1
解法：構(gòu)造樹的時(shí)候可以有方向地存沙峻，只存父親結(jié)點(diǎn)，從下向上找到第一個(gè)人的所有祖先結(jié)點(diǎn)两芳，并標(biāo)記摔寨，再從下向上找第二個(gè)人的祖先結(jié)點(diǎn)，如果有某個(gè)結(jié)點(diǎn)已經(jīng)被標(biāo)記過則輸出次結(jié)點(diǎn)怖辆，否則輸出-1
代碼：
#include<iostream>
#include<string>
#include<map>
using namespace std;
struct node{
string father;
bool visit;
};
map<string,node> s;
void find(string a)
{
if(s.count(a)){
s[a].visit=1;
if(s[a].father!="")
find(s[a].father);
}
else
s[a].visit=1;
return;
}
string find1(string b){
if(s.count(b)){
if(s[b].visit==1)
return b;
else
return find1(s[b].father);
}
else
return "-1";
}
int main()
{
int n;
string a,b;
cin>>n;
for(int i=0;i<n;i++){
cin>>a>>b;
s[b].father=a;
s[b].visit=0;
}
cin>>n;
for(int i=0;i<n;i++){
cin>>a>>b;
find(a);
cout<<find1(b)<<endl;
map<string,node>::iterator it;
for(it=s.begin();it!=s.end();it++)
it->second.visit=0;
}
}
