天梯题集——愿天下有情人都是失散多年的兄妹（隐藏条件）

冷不防 2022-12-24 01:51 90阅读 0赞

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

![t1][]  
![t2][]

#### 解题思路 ####

利用结构体读入每个 ID 下数据  
**隐藏条件：**标记父母的性别 （卡死个人）

假设判断 a，b 是否可通婚
    同性输出 “Never Mind”
    不同性 bfs标记 a 的五代内的祖先 check检查 b 五代内的祖先
    			b 五代内的祖先被标记过 输出“No”
    			b 五代内的祖先全部未被标记过 输出“Yes”

#include<bits/stdc++.h>
    using namespace std;
    bool judge[100010];
    int flag;
    struct node{ 
    	int fa, ma;
    	char sex;
    }num[100010];
    
    void bfs(int a, bool *judge, int k){ 
    	if(k==5) return;
    	int x = num[a].fa;
    	int y = num[a].ma;
    	if(x!=0&&x!=-1){ 
    		judge[x]=true;
    		bfs(x, judge, k+1);
    	}
    	if(y!=0&&y!=-1){ 
    		judge[y]=true;
    		bfs(y, judge, k+1);
    	}
    	return ;
    }
    
    void check(int a, bool *judge, int k){ 
    	if(k==5||flag) return;
    	int x = num[a].fa;
    	int y = num[a].ma;
    	if(x!=-1&&x!=0){ 
    		if(judge[x]){ 
    			flag=1;
    			return;
    		}
    		else
    			check(x, judge, k+1);
    	}
    	if(y!=-1&&y!=0){ 
    		if(judge[y]){ 
    			flag=1;
    			return;
    		}
    		else
    			check(y, judge, k+1);
    	}
    	
    	return ;
    }
    
    int main(){ 
    	int n;
    	cin>>n;
    	for(int i=0; i<n; i++){ 
    		int index;
    		cin>>index;
    		cin>>num[index].sex>>num[index].fa>>num[index].ma;
    		num[num[index].fa].sex = 'M';
    		num[num[index].ma].sex = 'F';
    	}
    	int k;
    	cin>>k;
    	for(int i=0; i<k; i++){ 
    		int a, b;
    		flag=0;
    		cin>>a>>b;
    		if(num[a].sex==num[b].sex){ 
    			cout<<"Never Mind\n";
    		}	
    		else{ 
    			memset(judge, false, sizeof(judge));
    			bfs(a, judge, 1);
    			check(b, judge, 1);
    			if(!flag)
    				cout<<"Yes\n";
    			else
    				cout<<"No\n";
    		}
    	}
    	
    	return 0;
    }

### 总结 ###

一开始没标记父母性别，想来想去都不知道哪里的问题。  
题目中的隐藏条件，再一次说明细节真的很重要。

[t1]: /images/20221120/094ede146c1c4fe28715751b72360072.png
[t2]: https://img-blog.csdnimg.cn/20201126124945544.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70#pic_center