问题描述：
已知人名构成的父子关系树（或者森林），对于给定的两个人名name1和name2，求其最近公共祖先。题目保证人名不重复。
分析：
当数据量不是很大询问不是很多的时候，利用C++ STL中的map和set容器可以很方便的实现。用map容器存储父子关系。对于每一个询问，先将从name1开始到树根的路径上的所有人名放入一个set容器，然后从name2开始向树根上溯，逐个检测人名是否已在set中即可。
我的代码：
1 #include <iostream> 2 #include <string> 3 #include <map> 4 #include <set> 5 6 using namespace std; 7 8 map<string, string> fa; 9 set<string> st; 10 11 int main() 12 { 13 int n, m; 14 while(cin>>n) 15 { 16 fa.clear(); 17 while(n--) 18 { 19 string s1, s2; 20 cin>>s1>>s2; 21 fa[s2] = s1; 22 } 23 cin>>m; 24 while(m--) 25 { 26 string name1, name2; 27 cin>>name1>>name2; 28 st.clear(); 29 while(fa.find(name1)!=fa.end()) 30 { 31 st.insert(name1); 32 name1 = fa[name1]; 33 } 34 st.insert(name1); 35 int sz = st.size(); 36 bool flag = false; 37 st.insert(name2); 38 if(sz==st.size()) 39 { 40 cout<<name2<<endl; 41 flag = true; 42 continue; 43 } 44 else 45 { 46 sz = st.size(); 47 while(fa.find(name2)!=fa.end()) 48 { 49 name2 = fa[name2]; 50 st.insert(name2); 51 if(sz==st.size()) 52 { 53 cout<<name2<<endl; 54 flag = true; 55 break; 56 } 57 else 58 { 59 sz = st.size(); 60 } 61 } 62 } 63 if(!flag) cout<<-1<<endl; 64 } 65 } 66 67 return 0; 68 }
题目链接：http://hihocoder.com/problemset/problem/1062