您当前的位置: 首页 > 

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

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

不牌不改 发布时间:2022-03-22 11:29:49 ,浏览量:0

题目

题目链接

题解

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;
}
关注
打赏
1662186765
查看更多评论
立即登录/注册

微信扫码登录

0.0891s