L2-016. 愿天下有情人都是失散多年的兄妹(深搜)*

时间:2023-07-05 20:50:02

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

参考博客

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int flag;
struct node
{
int dad,mom,sex,bh;
node():dad(),mom(),sex(),bh(-){}
}peo[];
void mark(int x,int p,int cs)
{
if(cs==||peo[x].dad==)
return ; if(peo[x].dad!=-)
{
mark(peo[x].dad,p,cs+);
peo[peo[x].dad].bh=p;
}
if(peo[x].mom!=-)
{
peo[peo[x].mom].bh=p;
mark(peo[x].mom,p,cs+);
}
}
void match(int x,int p,int cs)
{
if(cs==||peo[x].dad==||flag)
return ; if(peo[x].dad!=-)
{ if(peo[peo[x].dad].bh==p)
flag=;
else
match(peo[x].dad,p,cs+);
}
if(peo[x].mom!=-)
{ if(peo[peo[x].mom].bh==p)
flag=;
else
match(peo[x].mom,p,cs+);
} }
int main()
{
int n;
while(cin>>n)
{
int a,fa,ma;
char c;
for(int i=;i<n;++i)
{
cin>>a>>c>>fa>>ma; if(c=='M')
peo[a].sex=;
else
peo[a].sex=; peo[a].dad=fa;
peo[a].mom=ma; if(fa!=-)
peo[fa].sex=;
if(ma!=-)
peo[ma].sex=;
} int m,x,y;
cin>>m;
for(int i=;i<m;++i)
{
flag=;
cin>>x>>y;
int j;
if(peo[x].sex==peo[y].sex)
cout<<"Never Mind"<<endl;
else
{
mark(x,i,);
match(y,i,);
if(flag)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
}
}
}