搜索

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

输入格式:

输入第一行给出一个正整数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


做这个题的时候刚学了并查集查找父节点,仔细想想好像没法统计几代的问题。所以可以用dfs来标记每个人的五代,看看是否重复

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 100000;
vector<int> edge[maxn];
char sex[maxn + 100];
int ans,fa;

int que[maxn];
void dfs(int x, int s, int flag)
{

if(s >= 5)return;

if(flag == 0)
{
for(int i = 0; i < fa; i++)
{
if(x == que[i])
{
ans = 1;
return;
}
}
} else {
que[fa++]=x;
}
for(int i = 0; i < edge[x].size(); i++)
{
dfs(edge[x][i], s + 1, flag);
}
return;
}
int main()
{
int n;
cin >> n;

int x, y, z;
for(int i = 0; i < n; i++)
{
scanf("%d", &x);
cin >> sex[x];
cin >> y >> z;
if(y!=-1)
edge[x].push_back(y);
if(z!=-1)
edge[x].push_back(z);
sex[y] = 'M';
sex[z] = 'F';
}
int k;
cin >> k;
for(int i = 0; i < k; i++)
{
cin >> x >> y;
ans = 0;
if(sex[x] == sex[y])
printf("Never Mind\n");
else {
fa = 0;
dfs(x, 0, 1);
dfs(y, 0, 0);
if(ans)
printf("No\n");
else
printf("Yes\n");
}
}
}
script>