团体程序设计天梯赛
L2-030 冰岛人
并查集，使用myFather数组记录父节点。建树时处理字符串的输入，使用哈希表personID对名和编号进行映射。对两个家庭分别使用集合fml1和fml2记录，使用集合fmlCombined判断家庭是否存在重复的成员。
需要注意的是，需要判断公共的祖先节点是否出现在五代以内，否则测试点3和测试点6不能通过。具体地，在上一步之后，迭代枚举某一家庭祖先的父节点，如果另一家庭的集合（五代）中存在该节点，则说明不符合题意。
#include <bits/stdc++.h>
using namespace std;
map<string, int> personID; // 用于编号
vector<int> myFather, sex;
vector<string> temp; // 用于暂时存储关系字符串
int main(){
int n;
cin >> n;
myFather.resize(n);
sex.resize(n);
temp.resize(n);
for(int i = 0; i <= n - 1; i++) myFather[i] = i;
for(int i = 0; i <= n - 1; i++){
string ming, xing;
cin >> ming >> xing;
personID[ming] = i;
temp[i] = xing;
}
for(int i = 0; i <= n - 1; i++){
if((int)temp[i].length() >= 4 && temp[i].substr((int)temp[i].length() - 4, 4) == "sson"){
string fa = temp[i].substr(0, (int)temp[i].length() - 4);
auto faID = personID.find(fa);
myFather[i] = faID->second;
sex[i] = 1;
}
else if((int)temp[i].length() >= 7 && temp[i].substr((int)temp[i].length() - 7, 7) == "sdottir"){
string fa = temp[i].substr(0, (int)temp[i].length() - 7);
auto faID = personID.find(fa);
myFather[i] = faID->second;
sex[i] = 0;
}
else if((int)temp[i].length() >= 1 && temp[i][(int)temp[i].length() - 1] == 'm'){
sex[i] = 1;
}
else if((int)temp[i].length() >= 1 && temp[i][(int)temp[i].length() - 1] == 'f'){
sex[i] = 0;
}
}
int m;
cin >> m;
for(int i = 0; i <= m - 1; i++){
string ming1, xing1, ming2, xing2;
cin >> ming1 >> xing1 >> ming2 >> xing2;
auto id1 = personID.find(ming1), id2 = personID.find(ming2);
if(id1 == personID.end() || id2 == personID.end()) cout << "NA" << endl;
else if(sex[id1->second] == sex[id2->second]) cout << "Whatever" << endl;
else{
set<int> fml1, fml2, fmlCombined;
int num1 = id1->second, num2 = id2->second;
fml1.insert(num1), fml2.insert(num2);
for(int j = 0; j <= 2; j++){
num1 = myFather[num1], num2 = myFather[num2];
fml1.insert(num1), fml2.insert(num2);
}
fmlCombined.insert(fml1.begin(), fml1.end());
fmlCombined.insert(fml2.begin(), fml2.end());
if((int)fmlCombined.size() < (int)fml1.size() + (int)fml2.size()) cout << "No" << endl;
else{
int flag = 1;
while(num1 != myFather[num1]){
num1 = myFather[num1];
if(fml2.find(myFather[num1]) != fml2.end()){
cout << "No" << endl;
flag = 0;
break;
}
}
while(num2 != myFather[num2]){
num2 = myFather[num2];
if(fml1.find(myFather[num2]) != fml1.end()){
cout << "No" << endl;
flag = 0;
break;
}
}
if(flag) cout << "Yes" << endl;
}
}
}
return 0;
}