[BFS]愿天下有情人都是失散多年的兄妹

题目概述:

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

时间限制

200 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

呵呵。大家都知道五服以内不得通婚,即两个人最近的共同祖先如果在五代以内(即本人、父母、祖父母、曾祖父母、高祖父母)则不可通婚。本题就请你帮助一对有情人判断一下,他们究竟是否可以成婚?

输入格式:

输入第一行给出一个正整数N(2 <= N <= 104),随后N行,每行按以下格式给出一个人的信息:

本人ID 性别 父亲ID 母亲ID

其中ID是5位数字,每人不同;性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考,则相应的ID位置上标记为-1。

接下来给出一个正整数K,随后K行,每行给出一对有情人的ID,其间以空格分隔。

注意:题目保证两个人是同辈,每人只有一个性别,并且血缘关系网中没有乱伦或隔辈成婚的情况。

输出格式:

对每一对有情人,判断他们的关系是否可以通婚:如果两人是同性,输出“Never Mind”;如果是异性并且关系出了五服,输出“Yes”;如果异性关系未出五服,输出“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
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

输出样例:

1
2
3
4
5
6
7
8
9
Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
No
1
分析:

利用广度优先搜索,将每个人及双亲放入集合mab中,假如集合长度为改变,则说明mab中已存在这个人,则证明双方是近亲。visit用来记录层数。五层时结束搜索。

AC代码BFS:

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>  
#include<set>
#include<queue>
#include<cstring>
#define MAXN 100005
using namespace std;
struct inf {
int fa;
int ma;
char sex;
};
inf node[MAXN];
int visit[MAXN];
bool flag[MAXN];
int N;
bool BFS(int x1,int x2) {
memset(visit, 0, sizeof(visit));
queue<int>family;
set<int>mab;
family.push(x1);
family.push(x2);
visit[x1] = 1;
visit[x2] = 1;
while (!family.empty()) {
int top = family.front();
family.pop();
int size = mab.size();
mab.insert(top);
if (mab.size() == size) {
return true;
break;
}
if (visit[top] <= 4) {
if (node[top].fa) {
family.push(node[top].fa);
visit[node[top].fa] += visit[top] + 1;
}
if (node[top].ma) {
family.push(node[top].ma);
visit[node[top].ma] += visit[top] + 1;
}
}
}
return false;
}
int main() {
cin >> N;
memset(node, 0, sizeof(node));
memset(flag, 0, sizeof(flag));
while (N--) {
int id, fa, ma;
char ch[2];
scanf("%d%s%d%d", &id, ch, &fa, &ma);
node[id].sex = ch[0];
flag[id] = true;
if (fa != -1) {
node[id].fa = fa;
node[fa].sex = 'M';
flag[fa] = true;
}
if (ma != -1) {
node[id].ma = ma;
node[ma].sex = 'F';
flag[ma] = true;
}
}
cin >> N;
while (N--) {
int per1, per2;
cin >> per1 >> per2;
if (node[per1].sex == node[per2].sex)
printf("Never Mind\n");
else {
if (BFS(per1, per2))
printf("No\n");
else
printf("Yes\n");
}
}
return 0;
}

文章结束了,但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!