L2-016 愿天下有情人都是失散多年的兄妹 (25 分)
摘要
Title: L2-016 愿天下有情人都是失散多年的兄妹 (25 分)
Tag: DFS
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
L2-016 愿天下有情人都是失散多年的兄妹 (25 分)
-
题意
呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？
-
思路
ps: 别忘了给父母也打上性别
当给出要查询的两点时，先dfs一个点，把5层以内的点全标记上，再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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111/*
* @Author: NEFU AB-IN
* @Date: 2022-04-21 15:25:25
* @FilePath: \ACM\GPLT\L2-016.CPP
* @LastEditTime: 2022-04-21 18:39:43
*/
using namespace std;
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
*/