L2-030 冰岛人
这种方式是找到最终的祖宗,其实如果中间的父节点就相同了就可以判断为同祖宗
bool check(string a, string b){
int cnt1 = 1, cnt2 = 1;
while(a != p[a]) a = p[a], cnt1 ++;
while(b != p[b]) b = p[b], cnt2 ++;
if(a == b && (min(cnt1, cnt2) >= 5)) return true;
else if(a != b) return true;
else return false;
}
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
map<string,string> p;//相当于前驱数组,存放父亲的名
map<string,int> sex;//存性别,-1表示女,1表示男
int n, m;
bool check(string a, string b){
map<string,int> cnt;//记录经过了几代人
for(int i=1; a!=""; i++){
cnt[a] = i;
a = p[a];
}
for(int i=1; b!=""; i++){
if(cnt[b]){//遇到同祖宗
if(cnt[b] >= 5 && i >= 5){
return true;
}else return false;
}
b = p[b];
}
return true;
}
int main(){
cin>>n;
while(n --){
string mi, xi;
cin>>mi>>xi;
if(xi.back() == 'm') sex[mi] = 1;
else if(xi.back() == 'f') sex[mi] = -1;
else if(xi.substr(xi.size()-4) == "sson") sex[mi] = 1, p[mi] = xi.substr(0, xi.size()-4);
else sex[mi] = -1, p[mi] = xi.substr(0, xi.size()-7);
}
cin>>m;
while(m --){
string m1, x1, m2, x2;
cin>>m1>>x1>>m2>>x2;
if(sex[m1] == 0 || sex[m2] == 0) cout<<"NA"<<endl;
else if(sex[m1] == sex[m2]) cout<<"Whatever"<<endl;
else if(check(m1, m2)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}