L2-016. 愿天下有情人都是失散多年的兄妹

心已赠人 2022-05-30 00:30 132阅读 0赞

# L2-016. 愿天下有情人都是失散多年的兄妹 #

时间限制

200 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？

**输入格式：**

输入第一行给出一个正整数N（2 <= N <= 104），随后N行，每行按以下格式给出一个人的信息：

本人ID 性别 父亲ID 母亲ID

其中ID是5位数字，每人不同；性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考，则相应的ID位置上标记为-1。

接下来给出一个正整数K，随后K行，每行给出一对有情人的ID，其间以空格分隔。

注意：题目保证两个人是同辈，每人只有一个性别，并且血缘关系网中没有乱伦或隔辈成婚的情况。

**输出格式：**

对每一对有情人，判断他们的关系是否可以通婚：如果两人是同性，输出“Never Mind”；如果是异性并且关系出了五服，输出“Yes”；如果异性关系未出五服，输出“No”。

**输入样例：**

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
    9
    00021 00024
    00019 00024
    00011 00012
    00022 00018
    00001 00004
    00013 00016
    00017 00015
    00019 00021
    00010 00011

**输出样例：**

Never Mind
    Yes
    Never Mind
    No
    Yes
    No
    Yes
    No
    No

有一个坑就是爸妈也可能被查询，所以输入的时候要吧爸妈的性别也设置一下。

用的dfs，搜5代就可以了。

#include<stdio.h>
    #include<string.h>
    #include<string>
    #include<math.h>
    #include<vector>
    #include<map>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int father[110000],mother[110000],s;
    struct people
    {
    	int sex,fa,ma;
    }f[110000];
    int dfs(int a,int b,int s)
    {
    	if(a==-1||b==-1)
    		return 1;
    	if((mother[a]!=-1&&mother[a]==mother[b])||(father[a]!=-1&&father[a]==father[b]))
    		return 0;
    	s++;
    	if(s>=5)
    		return 1;
    	return (dfs(mother[a],mother[b],s)&&dfs(father[a],father[b],s)&&dfs(mother[a],father[b],s)&&dfs(father[a],mother[b],s));
    }
    int main()
    {
    	int n,m,i,j,id,faa,maa,a,b;
    	char c;  
    	memset(mother,-1,sizeof(mother));
    	memset(father,-1,sizeof(father));
        scanf("%d",&n);      
        for(i=0;i<n;i++) 
    	{  
            scanf("%d %c %d %d",&id,&c,&faa,&maa);  
            f[id].fa=faa;
    		f[id].ma=maa;  
            if(c=='M') 
    		f[id].sex=0;  
            else
    		f[id].sex=1; 
    		father[id]=faa; 
    		mother[id]=maa;
      		f[faa].sex=0; 
            f[maa].sex=1;  
        }
    	scanf("%d",&m);
    	while(m--)
    	{	
    		scanf("%d%d",&a,&b);
    		if(f[a].sex==f[b].sex)
    		printf("Never Mind\n");
    		else
    		{
    			s=1;
    			if(dfs(a,b,s))
    			printf("Yes\n");
    			else
    			printf("No\n"); 
    		}
    	}
    }