L2-016 愿天下有情人都是失散多年的兄妹
链接:题目详情 - L2-016 愿天下有情人都是失散多年的兄妹 (pintia.cn)
思路:刚开始想用并查集,后来改用DFS,但确切来说只是用了它的一个简单的搜索功能。
先说最后卡住的点,题给测试数据中可能有老一辈的人,所以输入父母数据时,需要对父母Id增加性别信息记录,加了这个处理后,直接就通过了。
刚开始用了结构体数组,后来发现用不上,删了。可以用pair或者map写写试试。
#include<cstdio>
const int N=100005;
int n,m,dai,a,b,c;
bool wudai[N]={false};
char sexa[N];
int father[N],mother[N];
void init(){
for(int i=0;i<N;i++){
father[i]=-1;
mother[i]=-1;
}
}
void DFS(int x){
if(dai==5){
return;
}
dai++;
wudai[x]=true;
a=father[x];
if(a!=-1){
DFS(a);
}
b=mother[x];
if(b!=-1){
DFS(b);
}
dai--;
}
void DFS1(int x){
if(dai==5){
return;
}
dai++;
if(wudai[x])
c=1;
a=father[x];
if(a!=-1){
DFS1(a);
}
b=mother[x];
if(b!=-1){
DFS1(b);
}
dai--;
}
int main(){
int i,x,y,a,b,l,v,e;
char o;
init();
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d %c %d %d",&l,&o,&v,&e);
if(v!=-1){
father[l]=v;
sexa[v]='M';
}
if(e!=-1){
mother[l]=e;
sexa[e]='F';
}
sexa[l]=o;
}
scanf("%d",&m);
for(i=0;i<m;i++){
scanf("%d %d",&x,&y);
for(int j=0;j<N;j++){
wudai[j]=false;
}
if(sexa[x]==sexa[y])
printf("Never Mind\n");
else{
dai=0;
DFS(x);
c=0;
dai=0;
DFS1(y);
if(c==1){
printf("No\n");
}
else
printf("Yes\n");
}
}
return 0;
}