【GPLT-L2-16】愿天下有情人都是失散多年的兄妹（深度优先搜索，广度优先搜索的应用）
L2-016 愿天下有情人都是失散多年的兄妹 (25分)
呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？
输入格式：
输入第一行给出一个正整数N（2 N ），随后N行，每行按以下格式给出一个人的信息：
本人ID 性别 父亲ID 母亲ID
其中ID是5位数字，每人不同；性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考，则相应的ID位置上标记为-1。
接下来给出一个正整数K，随后K行，每行给出一对有情人的ID，其间以空格分隔。
注意：题目保证两个人是同辈，每人只有一个性别，并且血缘关系网中没有乱伦或隔辈成婚的情况。
输出格式：
对每一对有情人，判断他们的关系是否可以通婚：如果两人是同性，输出Never Mind；如果是异性并且关系出了五服，输出Yes；如果异性关系未出五服，输出No。
输入样例：
24
00001 M 01111 -1
00002 F 02222 03333
00003 M 02222 03333
00004 F 04444 03333
00005 M 04444 05555
00006 F 04444 05555
00007 F 06666 07777
00008 M 06666 07777
00009 M 00001 00002
00010 M 00003 00006
00011 F 00005 00007
00012 F 00008 08888
00013 F 00009 00011
00014 M 00010 09999
00015 M 00010 09999
00016 M 10000 00012
00017 F -1 00012
00018 F 11000 00013
00019 F 11100 00018
00020 F 00015 11110
00021 M 11100 00020
00022 M 00016 -1
00023 M 10012 00017
00024 M 00022 10013
9
00021 00024
00019 00024
00011 00012
00022 00018
00001 00004
00013 00016
00017 00015
00019 00021
00010 00011
输出样例：
Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
No解析
广度优先遍历：首先通过map集合分别存储每个人的性别，以及这个人的父亲和母亲的编号。
存储N个人的信息
通过这个人的性别M和F两个字符判断是男性还是女性（这里父亲和母亲的性别也要存起来（不用关心是否有母亲或者是否有父亲（-1表示不存在，这在判断是否能够通婚的过程中要用到）））
对于输出结果
首先判断是否为同性。
其次如果为异性，判断是否可以通婚。
这里我用广度优先搜索过程来解决：查找五代以内的人的信息（这里我用了一个vector数组来存储每个人的辈分（差不多就是树的深度，但是这里的人的家族信息是一个图结构），初始化所有人的辈分为零）。对于要查找的两个人的编号，将这两个人的辈分设置为1。申请一个队列，将这两个人进入队列，然后开始进行广度优先搜索。
取出队头元素，出队，并利用set集合来存储每个人以及每个人祖先（父亲母亲）。首先判断set集合的大小，然后将队头元素添加进set集合中（判断加入前与加入后set集合的大小是否发生变化，如果没有发生变化说明有相同元素存在，即公共祖先，直接返回false即可）将队头元素的父亲和母亲（如果父亲和母亲编号不是-1才说明存在）分别加入队列中（父亲和母亲的辈分为其辈分加1，即比儿子的辈分大一）（如果发现队头元素的辈分，即辈分大于4（超出了五代以外）就不需要在进行入队操作了，我只判断五代以内是否发现相同的祖先）。
另外在判断队头元素是否要对其母亲或父亲进行操作的时候还要判断这个队头元素（即这个人是否在表中存在信息，也可以说某个人的父亲或者母亲在表中没有信息，就默认不用判断了！！！！）利用map集合存储每个人的信息，如果不在表中map集合里的话，它们的父亲母亲会被默认为0，不会设置为-1。所以这种情况一定要注意利用continue灵活的跳过这种特殊条件！！！！
using namespace std;using pii = pair<int,int>;int N,K;map<int,pii> peo;map<int,int> sex;bool check(int mes1,int mes2){queue<int> pq;//带查找的两个元素入队pq.push(mes1);pq.push(mes2);//设置set集合用来判断是否有共同祖先set<int> ms;//所有结点（人）的辈分默认为0vector<int> level(100010,0);//带查找的两个人的辈分设置为1level[mes1] = 1;level[mes2] = 1;while (!pq.empty()){ //取出队头元素int v = pq.front();pq.pop();//出队列//计算加入之前的set集合中的人数int nu = ms.size();//将这个人加入的set集合。ms.insert(v);//如果发现加入前和加入后元素个数没有变化说明存在相同祖先（即编号相同的元素，这正是利用了set集合不存储//相同元素的特点if(ms.size() == nu)return false;//结点是否存在（信息表中是否存在这个人）if(peo.count(v) == 0)continue;//只有辈分小于5的才判断if(level[v] <= 4){//得到这个人父亲母亲int fa = peo[v].first;int ma = peo[v].second;//存在父亲或者母亲的话加入到队列（辈分为儿子的辈分加一）if(fa != -1){pq.push(fa);level[fa] = level[v] + 1;}if(ma != -1){pq.push(ma);level[ma] = level[v] + 1;}}}return true;}int main(){cin>>N;while (N--){int a,af,am;char c;cin>>a>>c>>af>>am;peo[a]= make_pair(af,am);if(c == 'M')sex[a] = 1;if(c == 'F')sex[a] = 0;sex[af] = 1;sex[am] = 0;}cin>>K;while (K--){int stu1,stu2;cin>>stu1>>stu2;if(sex[stu1] == sex[stu2])cout<<"Never Mind"<<endl;elsecout<<(check(stu1,stu2) ? "Yes\n" : "No\n");}return 0;}
广度优先搜索解法：
在存储个人信息的过程中利用两个图。一个图用来存储该人的父亲和母亲(父结点）。另一个图用来存储它的下一代（即儿子）。
判断五代以内：
首先将第一个人的五代之内的所有人（包括自己）存储到一个set集合中，在存储过程中每个人要确定它的辈分（初始值第一个人的辈分为1）通过广度优先搜索，将与它相连的所有结点（与他之间的距离不大于5的点）加入到set集合中(超出5的要跳过，继续后面的结点进行判断)。
然后查看set集合中的每个元素五代以内包含五代是否存在第二个人（即另一个待测试的人）。同样对set集合中的每一个人进行广度搜索查看是否在五代以内包含五代的所有结点中存在第二个人。
整个过程结束之后仍然没有发现五代以内存在第二个人就说明，这个两个人可以通婚。
即利用两次广度优先搜索来判断。
using namespace std;using pii = pair<int,int>;//一个存储父结点，一个存储子结点map<int,vector<int> > G,rG;//性别map<int,char> gender;int N,K;bool judge(int x,int y){queue<pii> pq;//人的编号，以及辈分（从一开始）pq.push(make_pair(x,1));//第一个人以及第一个人五代以内的人的集合set<int> ms;while (!pq.empty()){auto v = pq.front();pq.pop();//超过五代就跳过此次循环（这个人丢掉）if(v.second > 5)continue;//五代以内就加入到集合中ms.insert(v.first);//在将其邻接点，父亲母亲加入到测试队列中（父结点）for(auto w : G[v.first])pq.push(make_pair(w,v.second+1));}//对x五代以内家族每个人判断其五代以内是否有yfor(auto w : ms){queue<pii> pq;//选择的结点查看五代以内是否有ypq.push(make_pair(w,1));while (!pq.empty()){auto v = pq.front();pq.pop();//前提是这个人必须是五代以内if(v.second > 5)continue;//这个人是y就直接跳出（找到答案）if(v.first == y)return false;//通过反图来测试子结点（儿子）for(auto i : rG[v.first])pq.push(make_pair(i,v.second+1));}}return true;}int main(){cin>>N;while (N--){int id,father_id,mother_id;char c;cin>>id>>c>>father_id>>mother_id;gender[id] = c;if(father_id != -1){gender[father_id] = 'M';G[id].push_back(father_id);rG[father_id].push_back(id);}if(mother_id != -1){gender[mother_id] = 'F';G[id].push_back(mother_id);rG[mother_id].push_back(id);}}cin>>K;while (K--){int na,nb;cin>>na>>nb;if(gender[na] == gender[nb])cout<<"Never Mind"<<endl;elsecout<<(judge(na,nb) ? "Yes\n" : "No\n");}return 0;}
深度优先搜索利用根据输入数据得到的图信息，对两个测试人进行深度搜索，第一个人进行搜索的过程中所有节点是默认都没有访问过的（即只搜索五代以内的人即可，包含第五代）。
DFS中设置了一个边界条件大于等于5（如果这个人最大没有超过五代的人也是没关系的，这里只是规定了一个范围，深度搜索的搜索范围在五代以内，最深访问到第五代就结束，并且到达第五代是必须把第五代设置为true已经访问）。
然后第二个人进行第二次深度优先搜索测试，如果这个过程中遇到有节点访问过（即说明和第一个人有公共祖先）。
vector<bool> visited(100100,false);bool flag;void DFS(int x,int sum){visited[x] = true;//sum等于5的时候就要在向下继续了，//对第一个人深搜的时候，会设置（当sum为第五代的时候设置为true）已经访问过if(sum >= 5)return;for(auto w : G[x]){if(!visited[w])DFS(w,sum+1);else //如果发现搜索过程中出现被访问过的结点，说明在第一次搜索的过程中被搜索过，即与第一个人有公共祖先{flag = false;return;}}}bool judge(int x,int y){//每次测试都要将visited初始化，并且标志值也要设置为true(每次测试标志可能变化)fill(visited.begin(),visited.end(),false);flag = true;//每次搜索起点都是标记为第一代DFS(x,1);DFS(y,1);return flag;}
利用递归方法求解：
map<int,pii> ms;bool DFS(int x,int y,int sum){//异性并且关系出了五服if(sum >= 5)return true;//ID未确定//或者是父亲或者母亲的id为-1找不到if(x == -1 || y == -1 || !ms.count(x) || !ms.count(y))return true;//两个人分别的父亲和母亲int fax = ms[x].first,max = ms[x].second;int fay = ms[y].first,may = ms[y].second;//是否为同一个父亲或者同一个母亲时if((fax > 0 && fax == fay && fay > 0)||(max == may && max > 0 && may > 0))return false;//判断下一代sum++++sum;//两个父亲是否 或者 第一个父亲和第二个母亲 或者 第一个的母亲和第二个的父亲 或者第一个的母亲和第二个母亲return (DFS(fax,fay,sum) && DFS(fax,may,sum) && DFS(max,fay,sum)&&DFS(max,may,sum));}bool judge(int x,int y){return DFS(x,y,1);}