呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？
输入格式：
输入第一行给出一个正整数N（2 <= N <= 104），随后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
分析：我用的方法是广度优先，然后把每个人和他们的祖先们压入一个set里面，判断set前后有没有大小改变，如果没改变说明重复了，所以有相同祖先，所以就输出No，用level数组标记他们当前的层数在push一层的时候令他们的层数为上一层+1，一直到五层判断结束。如果结束了还没有输出过No，那么就输出yes。（其实后来想到可以用数组标记的方法，不用集合来这么复杂的。。）
有三个注意点：1.一开始有三个测试点不过，然后。。发现。。每次在输入的时候把它们父母的性别也要标记一下，因为！测试数据里面可能会判断某个人的父亲（但是不在给出的本人id的列表中），或者母亲和某个人是否能结婚。。。。也就是说测试数据里面如果出现了09999，它是某个人的父母，那么也可能会被判断。。所以。。所以。。要在输入的时候加上父母的性别的标记。。。PAT教我做人。。
【有可爱的小伙伴和我说不太明白第一个注意点的意思，我的意思是，测试用例里面，除了测试样例那样常规的9种询问的是否可以通婚的用例，还有可能会问02222和03333是否可以通婚，02222和04444是否可以通婚。但是我们不知道02222和03333和04444的父母是谁，所以就默认他们之间是没有血缘关系的，接下来考虑的就是他们的性别问题了，因为02222是男的（因为他是父亲嘛）而03333是女的，那就要输出可以通婚；同理，04444是男的，就要输出never mind~】
2.因为我开的是全局数组，用全局数组的时候就千万要记得，用完之后记得把它。。置回0啊啊啊。。。因为下一组测试数据用这个数组的时候可能会不小心用到了上一组测试数据保存的结果。。。就会出错了。。
3.用exist数组标记是否存在这个结点，否则避免不小心把0压入。。。到队列里面（就是求对于一个父母，他们可能不存在在本人id里面，那么把他们的孩子结点放入queue里面就会出现0.。不断标记0的话把0当他们的共同祖先可能会误输出No）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <cstdio> #include <set> #include <queue> #include <algorithm> using namespace std; struct node { int f, m, sex; }; node v[100010]; int level[100010]; bool exist[100010]; int main() { int n, m, id, father, mother, a, b; scanf("%d", &n); char c; for(int i = 0; i < n; i++) { scanf("%d %c %d %d", &id, &c, &father, &mother); v[id].f = father, v[id].m = mother; if(c == 'M') v[id].sex = 0; else v[id].sex = 1; exist[id] = true; v[father].sex = 0; v[mother].sex = 1; } scanf("%d", &m); for(int i = 0; i < m; i++) { fill(level, level + 100010, 0); scanf("%d%d", &a, &b); if(v[a].sex == v[b].sex) { printf("Never Mind\n"); continue; } queue<int> q; q.push(a); q.push(b); level[a] = 1; level[b] = 1; set<int> s; int flag = 0; while(!q.empty()) { int top = q.front(); q.pop(); int size = s.size(); s.insert(top); if(size == s.size()) { printf("No\n"); flag = 1; break; } if(exist[top] == false) continue; if(level[top] <= 4) { int fa = v[top].f; int mo = v[top].m; if(fa != -1) { q.push(fa); level[fa] = level[top] + 1; } if(mo != -1) { q.push(mo); level[mo] = level[top] + 1; } } } if(flag == 0) printf("Yes\n"); } return 0; } |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼
❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼
❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版
