题目
题目链接
题解DFS。
孩子向父母方向连边,将孩子视为根节点。
首先判断输入两个人的性别,如果不同再分别以二者为起点进行dfs,前者五服之内的亲属都标记一下,以后者为起点dfs,如果遇到了标记的人,那么说明五服之内存在公共祖先,不可以结婚。
我一直在思考怎么用倍增法计算最近公共祖先,但是死活想不出来,因为一个孩子有一对父母,这和一般的公共祖先还不一样,最近公共祖先是一个父节点有多个节点,而本题是一个子节点有多个父节点;如果将孩子理解为父节点,父母理解为子节点,虽然构造出最近公共祖先问题,但是并不知道要计算哪两个子节点的公共祖先,所以本质上不是一类问题。
代码#include
using namespace std;
const int N = 1e4+10, M = 1e6+10;
int flag, n, k;
int e[M], ne[M], h[M], idx;
int gender[M], st[M];
void add (int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs (int x, int dp) {
if (flag == 1) return ;
if (dp >= 5) return ;
for (int i = h[x]; ~i;i = ne[i]) {
int j = e[i];
if (st[j]) {
flag = 1;
return ;
}
st[j] = 1;
dfs (j, dp + 1);
}
}
int main () {
cin >> n;
memset (h, -1, sizeof h);
memset (gender, -1, sizeof gender);
for (int i = 0;i > id >> sex >> fid >> mid;
if (fid != -1) add (id, fid), gender[fid] = 1;
if (mid != -1) add (id, mid), gender[mid] = 0;
gender[id] = (sex == 'M');
}
cin >> k;
while (k --) {
int a, b;
cin >> a >> b;
if (gender[a] == gender[b] || gender[a] == -1 || gender[b] == -1)
puts("Never Mind");
else {
memset (st, 0, sizeof st);
st[a] = 1;
st[b] = 1;
flag = 0;
dfs (a, 1);
dfs (b, 1);
if (flag) puts ("No");
else puts ("Yes");
}
}
return 0;
}