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

发表于 | 分类于 ， | 热度 ℃
字数统计: 922 | 阅读时长 ≈ 5

题目概述：

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;  
}
文章结束了，但我们的故事还在继续
坚持原创技术分享，您的支持将鼓励我继续创作！