hihocoder#1062 : 最近公共祖先·一
传送门
思路：用map存下每个节点及其父节点。每次询问时建立一个集合，将name1的所有祖先放入集合。
自底向上的遍历name2的所有祖先，如果在集合中则为最近公共祖先。
#include<iostream> #include<algorithm> #include<queue> #include<cmath> #include<cstring> #include<cstdio> #include<map> #include<vector> #include<string> #include<set> using namespace std; #define INF 0x3f3f3f3f const int maxn = 1001; int main() { int n,m; string name1,name2; cin>>n; map<string,string>mp; while(n--) { cin>>name1>>name2; mp[name2]=name1; } cin>>m; while(m--) { set<string>s; cin>>name1>>name2; while(name1!="") { s.insert(name1); name1=mp[name1]; } bool flag=false; while(name2!="") { if(s.find(name2)!=s.end()) { flag=true; break; } else name2=mp[name2]; } if(!flag)cout<<-1<<endl; else cout<<name2<<endl; } return 0; }
