传送门

题面描述：

给出一个家族的种种关系和两头牛 a ， b 问这两头牛是什么关系，输出格式要求为X1 is the XXXXX of X2。要求中间的亲属关系为长辈对晚辈，如：X1 is the mother of X2 而不是 X2 is the son of X1。

题目分析：

这题一开始看特别乱，又是mother又是aunt又是cousin的那么多关系，其实只要把一些重要的步骤单独写成函数就会顺畅一点，并且还要知道这题考的是查找最近公共祖先这一点。那就先把两个重要的函数写出来呗。
第一个是findfar(string a)，目的是查找字符串 a 的祖先并返回，若没有则返回空字符串“”。
第二个是isancestor(string a,string b)，作用是判断 a 是否为 b 的祖先，如果是，则返回 a 和 b 之间的距离，不是则返回-1.
这时候我们就要开始找 a 和 b 的最近公共祖先了，先假设公共祖先是 a ，利用上面的两个函数查找的同时计算最后找到的公共祖先 common 与 a 的距离，这时候也能得到 common 与 b 的距离，根据这个距离就能知道 a 与 b 的关系。后面记得要考虑 a 和 b 辈分谁大谁小，输出的情况还有些麻烦，要仔细想想不能有疏漏。

代码：

#include<algorithm>
#include<stdio.h> 
#include<iostream>
#include<string.h> 
#include<queue>
#include<vector>
using namespace std;
string a,b,far[105],cow[105];
int i,n;string findfar(string a){for(int i=1;i<=n;i++) if(a==cow[i]) return far[i];return "";
}int isancestor(string a,string b){//a是b的祖先吗,是就返回距离 int dis=0;while(b!=""){if(a==b) return dis;b=findfar(b);dis++;}return -1;
}int main(){string a,b;cin>>n>>a>>b;for(i=1;i<=n;i++) cin>>far[i]>>cow[i];string common=a;int disa=0,disb=0;while(common!=""){//找最近公共祖先 if(isancestor(common,b)!=-1) break;common=findfar(common);disa++;//a与最近公共祖先的距离 }if(common==""){cout<<"NOT RELATED";return 0;}disb=isancestor(common,b);if(disa>1&&disb>1) cout<<"COUSINS";else if(disa==1&&disb==1) cout<<"SIBLINGS";else{if(disa>disb) swap(a,b),swap(disa,disb);//让a辈分比b高 cout<<a<<" is the ";int dif=disb-disa;for(dif;dif>=3;dif--) cout<<"great-";if(a==common&&dif==2) cout<<"grand-";if(a==common) cout<<"mother";if(a!=common&&dif==2) cout<<"great-";if(a!=common) cout<<"aunt";cout<<" of "<<b;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！