7-2 愿天下有情人都是失散多年的兄妹
样例
2400001 M 01111 -100002 F 02222 0333300003 M 02222 0333300004 F 04444 0333300005 M 04444 0555500006 F 04444 0555500007 F 06666 0777700008 M 06666 0777700009 M 00001 0000200010 M 00003 0000600011 F 00005 0000700012 F 00008 0888800013 F 00009 0001100014 M 00010 0999900015 M 00010 0999900016 M 10000 0001200017 F -1 0001200018 F 11000 0001300019 F 11100 0001800020 F 00015 1111000021 M 11100 0002000022 M 00016 -100023 M 10012 0001700024 M 00022 10013900021 0002400019 0002400011 0001200022 0001800001 0000400013 0001600017 0001500019 0002100010 00011
#include<iostream>#include<map>#include<vector>using namespace std;typedef struct pp{int id;char sex;int father;int mother;int flag;}person;vector<person> vec;map<int,int> mapp;int num;void dfs1(int id,int l){if(mapp.find(id)==mapp.end())return;else id=(*(mapp.find(id))).second; if(l==5)return; // 五服即dfs五层vec[id].flag=num; // 标记dfs1(vec[id].father,l+1); dfs1(vec[id].mother,l+1);}bool dfs2(int id,int l){if(mapp.find(id)==mapp.end())return false;else id=(*(mapp.find(id))).second;if(l==5)return false;if(vec[id].flag==num)return true; // 重复return (dfs2(vec[id].father,l+1) || dfs2(vec[id].mother,l+1)); }bool isfind(person x,person y){if(x.father!=-1)dfs1(x.father,1);if(x.mother!=-1)dfs1(x.mother,1); // 对第一个人的五服做标记return (dfs2(y.father,1) || dfs2(y.mother,1)); // 查询五服之内是否重复}int main(){int n;int newnum=0;cin>>n;personmax=n;for(int i=0;i<n;i++){int a,b,c;char d;cin>>a;getchar();cin>>d;cin>>b>>c;if(mapp.find(a)==mapp.end()){vec.push_back((person){a,d,b,c,0}); // 添加本人mapp.insert(pair<int,int>(a,newnum)); // 建立id与vec下标的映射(可用散列表实现)newnum++;}else{int v=(*(mapp.find(a))).second; // 修改本人(即前面的父亲或母亲)vec[v]=(person{a,d,b,c,0});}if(b!=-1 && mapp.find(b)==mapp.end()){// 避免兄弟姐妹的情况vec.push_back((person){b,'M',-1,-1,0}); // 添加父亲mapp.insert(pair<int,int>(b,newnum));newnum++;}if(c!=-1 && mapp.find(c)==mapp.end()){vec.push_back((person){c,'F',-1,-1,0}); // 添加父亲mapp.insert(pair<int,int>(c,newnum));newnum++;}}cin>>n;for(int i=0;i<n;i++){int a,b;cin>>a>>b;num++; // 用于标记不同对情人的查询a=(*(mapp.find(a))).second; b=(*(mapp.find(b))).second; if(vec[a].sex==vec[b].sex){cout<<"Never Mind"<<endl;continue;} // 同性无所谓2333if(isfind(vec[a],vec[b])){cout<<"No"<<endl;continue;}else cout<<"Yes"<<endl;}return 0;}
