天梯 - 愿天下有情人都是失散多年的兄妹（DFS公共祖先）
呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？
输入格式：
输入第一行给出一个正整数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
1 #include <bits/stdc++.h> 2 typedef long long LL; 3 const int INF=0x3f3f3f3f; 4 const double eps =1e-8; 5 const int mod=1e9+7; 6 const int maxn=1e5+10; 7 using namespace std; 8 9 int op[maxn];//性别男=1，女=0 10 int fa[maxn]; 11 int mo[maxn]; 12 13 int Judge(int a,int b,int step) 14 { 15 if(a==-1||b==-1||step>=5) return 1;//如果有一方无法考证或到了第5代就算符合，注意是>=5 16 int af=fa[a], am=mo[a]; 17 int bf=fa[b], bm=mo[b]; 18 if(af!=-1&&af==bf) return 0; //如果父母亲都可考证且相等，不符合 19 if(am!=-1&&am==bm) return 0; 20 return Judge(af,bf,step+1)&&Judge(af,bm,step+1)&&Judge(am,bf,step+1)&&Judge(am,bm,step+1); 21 //如果没有超过五代，就要考虑一下他们的父母两两之间是不是近亲 22 } 23 24 int main() 25 { 26 #ifdef DEBUG 27 freopen("sample.txt","r",stdin); 28 #endif 29 30 int n,m; 31 memset(fa,-1,sizeof(fa)); 32 memset(mo,-1,sizeof(mo)); 33 scanf("%d",&n); 34 for(int i=1;i<=n;i++) 35 { 36 int id,a,b; 37 char str[5]; 38 scanf("%d %s %d %d",&id,str,&a,&b); 39 fa[id]=a; mo[id]=b; 40 if(a!=-1) op[a]=1; //父母的性别也需要设置 41 op[id]= str[0]=='M'? 1:0; 42 } 43 scanf("%d",&m); 44 for(int i=1;i<=m;i++) 45 { 46 int a,b; 47 scanf("%d %d",&a,&b); 48 if(op[a]^op[b]==0) printf("Never Mind\n"); 49 else 50 { 51 if(Judge(a,b,1)) printf("Yes\n"); 52 else printf("No\n"); 53 } 54 } 55 56 return 0; 57 }
第二种方法：
参考于：https://blog.csdn.net/qq_37708702/article/details/79596602
用一个vis来判断，挺好写的。。
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 typedef struct Node{ 5 char sex; 6 int fId; 7 int mId; 8 }Node; 9 Node p[100001]; 10 int flag,visited[100001]; 11 void f(int a,int sum){ 12 if(sum > 5 || a == -1 || a == 0)//如果代数大于5代,或者a==-1,说明都不在人世,注意是>5 13 //或者a==0说明没有被赋值,直接返回 14 return; 15 visited[a]++;//记录被访问的次数 16 if(visited[a] >= 2)//如果五代以内的同一个人被访问超过2次,说明在五代之内有共同的祖先 17 flag = 0; 18 f(p[a].fId,sum + 1);//递归调用,a的父亲,代数+1 19 f(p[a].mId,sum + 1);//递归调用,a的母亲,代数+1 20 return; 21 } 22 int main(){ 23 int n,selfId,fId,mId,k,a,b; 24 char c; 25 scanf("%d",&n); 26 for(int i = 0;i < n;i++){ 27 scanf("%d %c%d%d",&selfId,&c,&fId,&mId); 28 p[selfId].sex = c;//记录自己的性别 29 p[selfId].fId = fId;//记录父亲的Id 30 p[selfId].mId = mId; 31 p[fId].sex = 'M';//记录自己父亲的性别,否则,可能会漏掉 32 p[mId].sex = 'F';//记录自己母亲的性别,否则,可能会漏掉 33 } 34 scanf("%d",&k); 35 while(k--){ 36 flag = 1;//标记变量,默认为1 37 memset(visited,0,sizeof(visited));//每循环一次,必须进行一次初始化 38 scanf("%d%d",&a,&b); 39 if(p[a].sex == p[b].sex){ 40 printf("Never Mind\n"); 41 continue; 42 } 43 f(a,1);//以a为起点,代数为一代,进行寻找 44 f(b,1);//以a为起点,代数为一代,进行寻找 45 if(flag) 46 printf("Yes\n"); 47 else 48 printf("No\n"); 49 } 50 return 0; 51 }
-
原文链接: https://www.cnblogs.com/jiamian/p/12578251.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/376872
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
