hihoCoder 1062 : 最近公共祖先·一（map+lca）

2019-11-11 05:01:16

字体：大中小

来源：转载

供稿：网友

题目链接：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;}

上一篇：面试：从一个列表中删除指定数

下一篇：C# SendKeys用法