愿天下有情人都是失散多年的兄妹 (25 分)
呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？
输入格式：
输入第一行给出一个正整数N（2 ≤ N ≤104），随后N行，每行按以下格式给出一个人的信息：
本人ID 性别 父亲ID 母亲ID
其中ID是5位数字，每人不同；性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考，则相应的ID位置上标记为-1。
接下来给出一个正整数K，随后K行，每行给出一对有情人的ID，其间以空格分隔。
注意：题目保证两个人是同辈，每人只有一个性别，并且血缘关系网中没有乱伦或隔辈成婚的情况。
输出格式：
对每一对有情人，判断他们的关系是否可以通婚：如果两人是同性，输出Never Mind；如果是异性并且关系出了五服，输出Yes；如果异性关系未出五服，输出No。
输入样例：
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
输出样例：
Never MindYesNever MindNoYesNoYesNoNo
这个题以前明明做过的,可是这一次就是一直不对,到最后调试时才明白,犯了一个非常细节性的错误,在bfs函数中定义bool类型的inq数组时没有初始化,很神奇,第一次执行一个查看两个人时候可以联姻是是对的,因为他的值是false,但是一旦这个false在运行过程中发生了变化,即变为true,那么由于没有初始化的缘故,函数调用结束后数组并没有没释放掉,而是依旧存在,所以值仍然是true,这似乎跟老师讲的函数调用结束后空间就会被收回不同,所以我就是栽在了这里,大家引以为戒,定义的变量不是全局变量一定要记得初始化,别再栽我这个跟头了…
#include<iostream>#include<vector>#include<queue>using namespace std;int n;int father[100005];int mother[100005];int lev[100005];char sex[100005];vector<int> v[100005];bool bfs(int s,int w){bool inq[100005]={};queue<int> q;q.push(s);q.push(w);inq[s]=true;inq[w]=true;lev[s]=1;lev[w]=1;while(!q.empty()){int t=q.front();q.pop();if(lev[t]==5)return true;if(father[t]!=-1&&inq[father[t]]==false){q.push(father[t]);lev[father[t]]=lev[t]+1;//cout<<lev[t];inq[father[t]]=true;}else if(father[t]!=-1&&inq[father[t]]==true){return false;}if(mother[t]!=-1&&inq[mother[t]]==false){q.push(mother[t]);lev[mother[t]]=lev[t]+1;inq[mother[t]]=true;}else if(mother[t]!=-1&&inq[mother[t]]==true){return false;}}return true;}int main(){cin>>n;char b;fill(father,father+100005,-1);fill(mother,mother+100005,-1);for(int i=0,a,c,d;i<n;i++){cin>>a;cin.ignore();cin>>sex[a]>>c>>d;if(c!=-1)v[c].push_back(a),father[a]=c,sex[c]='M';if(d!=-1)v[d].push_back(a),mother[a]=d,sex[d]='F';}int k;cin>>k;for(int i=0;i<k;i++){int a,b;cin>>a>>b;fill(lev,lev+100005,0);if(sex[a]==sex[b])cout<<"Never Mind\n";else if(bfs(a,b)==true)cout<<"Yes\n";else cout<<"No\n";fill(lev,lev+100005,0);}}
