題目鏈接：http://hihocoder.com/PRoblemset/problem/1062
【思路分析】給你n組人的關系，然后有m組詢問，每組給出兩個人名，讓你找出他們的最近的公共祖先是誰。然后可以用map直接儲存關系，然后暴力搞一下。 【AC代碼】
#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<iostream>#include<cmath>#include<map>using namespace std;int n,m;map<string,string > pre;//記錄父親和兒子pre[i]代表i的父親void FindAnscetor(string str1,string str2){ map<string,int >book; book[str1]=1; while(!pre[str1].empty()) { book[pre[str1]]=1; str1=pre[str1]; } //printf(".../n"); while(!str2.empty()) { if(book[str2]) { cout<<str2<<endl; return ; } str2=pre[str2]; } //printf("***/n"); printf("-1/n");}int main(){ while(~scanf("%d",&n)) { pre.clear(); string str1,str2; for(int i=1;i<=n;i++) { cin>>str1>>str2; pre[str2]=str1; } scanf("%d",&m); for(int i=1;i<=m;i++) { cin>>str1>>str2; FindAnscetor(str1,str2); } } return 0;}新聞熱點
疑難解答
