L2-016 愿天下有情人都是失散多年的兄妹 (25 分)

题意

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

ps: 别忘了给父母也打上性别
当给出要查询的两点时，先dfs一个点，把5层以内的点全标记上，再dfs另一个点，如果遇到标记的点，那么说明他俩不能在一起

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-04-21 15:25:25
* @FilePath: \ACM\GPLT\L2-016.CPP
* @LastEditTime: 2022-04-21 18:39:43
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;

const int N = 100010;
vector<int> g[N];
int n, k, flag, st[N];

unordered_map<int, char> vis;

void dfs(int u, int cnt, int type)
{
    if (cnt >= 5)
        return;
    if (type)
        st[u] = 1;
    if (st[u] && !type)
    {
        flag = 1;
        return;
    }
    for (auto v : g[u])
    {
        dfs(v, cnt + 1, type);
    }
}

signed main()
{
    IOS;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int id, fa, ma;
        char op;
        cin >> id >> op >> fa >> ma;
        vis[id] = op;
        if (fa != -1)
            g[id].push_back(fa), vis[fa] = 'M';
        if (ma != -1)
            g[id].push_back(ma), vis[ma] = 'F';
    }

    cin >> k;
    for (int i = 1; i <= k; ++i)
    {
        int u, v;
        cin >> u >> v;
        if (vis[u] == vis[v])
        {
            cout << "Never Mind\n";
        }
        else
        {
            flag = 0;
            memset(st, 0, sizeof st);
            dfs(u, 0, 1);
            dfs(v, 0, 0);
            if (!flag)
                cout << "Yes\n";
            else
                cout << "No\n";
        }
    }

    return 0;
}
/*
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
1
00022 00018
*/