PAT L2-016. 愿天下有情人都是失散多年的兄妹
原题链接
简单
作者:
青丝蛊
,
2021-04-13 16:08:50
,
所有人可见
,
阅读 282
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
char sex[N];
vector<int> v[N];
int dis[N];
bool bfs(int x, int y)
{
memset(dis, 0, sizeof dis);
queue<int> que;
que.push(x);
que.push(y);
dis[x] = dis[y] = 1;
while (que.size())
{
int t = que.front();
que.pop();
if (dis[t] == 5) return true;
for (auto c : v[t])
{
if (dis[c]) return false; // 五代内出现了共同祖宗
dis[c] = dis[t] + 1;
que.push(c);
}
}
return true;
}
int main()
{
int n;
cin >> n;
while (n--)
{
int x, a, b;
cin >> x;
cin >> sex[x] >> a >> b;
// a!=-1, 父母也要标注性别
if (~a) v[x].push_back(a), sex[a] = 'M';
if (~b) v[x].push_back(b), sex[b] = 'F';
}
cin >> n;
while (n--)
{
int a, b;
cin >> a >> b;
if (sex[a] == sex[b]) puts("Never Mind");
else cout << (bfs(a, b) ? "Yes\n" : "No\n");
}
return 0;
}