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

题目

题目链接

题解

DFS。

孩子向父母方向连边，将孩子视为根节点。

首先判断输入两个人的性别，如果不同再分别以二者为起点进行dfs，前者五服之内的亲属都标记一下，以后者为起点dfs，如果遇到了标记的人，那么说明五服之内存在公共祖先，不可以结婚。

我一直在思考怎么用倍增法计算最近公共祖先，但是死活想不出来，因为一个孩子有一对父母，这和一般的公共祖先还不一样，最近公共祖先是一个父节点有多个节点，而本题是一个子节点有多个父节点；如果将孩子理解为父节点，父母理解为子节点，虽然构造出最近公共祖先问题，但是并不知道要计算哪两个子节点的公共祖先，所以本质上不是一类问题。

代码

#include <bits/stdc++.h>
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 < n;i ++) {
		int id, fid, mid;
		char sex;
		cin >> 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;
}