7-51 愿天下有情人都是失散多年的兄妹——dfs

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

输入格式：
输入第一行给出一个正整数N（2 ≤ N ≤10^4），随后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

分析

1. 此题就是从自己这一代开始，向上递归5次，判断是否有相同的祖先（向上递归一次，就是查情侣的父亲或者母亲…是否相同；向上递归两次，就是查爷爷奶奶…依次判断）；
2. 正好结构体每个人都存了双亲的的id，直接在dfs函数中，情侣的爸爸妈妈互查，各自组合有A22种组合，4层dfs（见代码鞥更好理解）；然后加几个判断条件，如果存在一方去世，就不用比了，无法比较，因为都去世了，都不知道是否存在关系，直接return；然后如果id1==id2那就是祖先相同（理解为情侣两人的爷爷是同一个人或者奶奶同一人…，哈哈哈有点bt，但便于理解），那就打个flag标记；
3. 细节：需要初始化每个id的双亲，不然有的祖先没设置双亲；需要设置父母的性别,下面要判断同姓不能通婚用；dfs中的男爸+女妈组合，不要觉得不合适，以为虽然男爸女妈不会是同一个人，但是男爸女妈的上一层可能就是同一个人了；
4. 玄学：我把cin>>n放在了初始化每个人的双亲上面，编译器自测通过，pta测试直接WA，看下pta的运行测试，只输出了第一个结果，但是编译器结果全输出了对着呢，pta就是不通过，调了多半天，哎…；

#include

using namespace std;

struct node {
    char gender;
    int fatherId, motherId;
};
int n, k, flag;
node no[100010];

//u为代数
void dfs(int u, int id1, int id2) {
    //五代之内
    if (u == 5)
        return;
    //存在一方去世，就不用比了，无法比较
    if (id1 == -1 || id2 == -1)
        return;
    //说明祖先是同一个人
    if (id1 == id2) {
        flag = 1;
        return;
    }

    //父母互查，A22种组合
    dfs(u + 1, no[id1].fatherId, no[id2].fatherId);//男爸+女爸
    dfs(u + 1, no[id1].motherId, no[id2].motherId);//男妈+女妈
    dfs(u + 1, no[id1].fatherId, no[id2].motherId);//男爸+女妈
    dfs(u + 1, no[id1].motherId, no[id2].fatherId);//男妈+女爸
}

int main() {
    //cin >> n;  需要在初始化后再输入n，不然oj WA,玄学
    //初始化，不然有的祖先没设置双亲
    for (int i = 1; i <= 100010; ++i) {
        no[i].fatherId = no[i].motherId = -1;
    }
    cin >> n;
    int id;
    for (int i = 0; i < n; ++i) {
        cin >> id;
        cin >> no[id].gender >> no[id].fatherId >> no[id].motherId;
        //设置父母的性别,下面要判断同姓不能通婚用
        if (no[id].fatherId != -1)
            no[no[id].fatherId].gender = 'M';
        if (no[id].motherId != -1)
            no[no[id].motherId].gender = 'F';
    }
    cin >> k;
    int id1, id2;
    while (k--) {
        cin >> id1 >> id2;
        if (no[id1].gender == no[id2].gender) {
            //不能搞基哦
            cout << "Never Mind" << endl;
            continue;
        }
        dfs(0, id1, id2);
        if (flag) {
            //未出五服
            cout << "No" << endl;
        } else {
            cout << "Yes" << endl;
        }
        flag = 0;
    }
    return 0;
}

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