BFS GPLT L2-016 愿天下有情人都是失散多年的兄妹

题目链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805061769609216

分析：一开始以为是并查集。。。。。没救了，一看到这种亲属关系的就想往并查集靠

用level数组标记层次，在五层前都可以一遍遍的BFS

用个set，每次从队列取出一个数装进集合，没变化就说明重复过了

注意要给父母也标性别，后面可能出现查询两个没有给出全部信息的人能不能结婚，如果父母没有被单独说过的话，我们就默认父母是合法的，性别也要弄清

exist数组就是来看一个人是不是给出了全部信息，如果不是并且性别相异，我们就认为是可行的

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int inf=<<;

 const double pi=acos(-);

 const int mod=;

 const int maxn=1e5+;

 const int maxm=;

 struct node{

     int f,m,sex;

 }a[maxn];

 bool exist[maxn];

 int main(){

     int n,id,fa,mo;scanf("%d",&n);

     char c;

     for(int i=;i<n;i++){

         scanf("%d %c %d %d",&id,&c,&fa,&mo);

         exist[id]=true;

         a[id].f=fa;a[id].m=mo;

         if(c=='M') a[id].sex=;

         if(c=='F') a[id].sex=;

         a[fa].sex=,a[mo].sex=;

     }

     int k,x,y;scanf("%d",&k);

     for(int i=;i<k;i++){

         scanf("%d%d",&x,&y);

         if(a[x].sex==a[y].sex){

             printf("Never Mind\n");

             continue;

         }

         int level[maxn];

         queue<int> q;

         q.push(x);q.push(y);

         level[x]=,level[y]=;

         set<int> s;bool flag=;

         while(!q.empty()){

             int top=q.front();q.pop();

             int size=s.size();

             s.insert(top);

             if(size==s.size()){//插进去一个值却发现集合大小没发生变化，说明另一方曾经插入过

                 printf("No\n");

                 flag=;break;

             }

             if(!exist[top])continue;//说明他不是我们n个id中的一个，不知道他的父母是谁，不用再考虑了

             fa=a[top].f,mo=a[top].m;

             if(fa!=-&&level[top]<){

                 q.push(fa);level[fa]=level[top]+;

             }

             if(mo!=-&&level[top]<){

                 q.push(mo);level[mo]=level[top]+;

             }

         }

         if(flag) cout<<"Yes\n";

     }

     return ;

 }