L2-016 愿天下有情人都是失散多年的兄妹 （25 分)
#include<bits/stdc++.h>
using namespace std;
int fa[100000];
int ma[100000];
int sex[100000];
bool dfs(int a,int b,int cnt)
{
if(a==-1||b==-1)return 1;
if(ma[a]!=-1&&ma[a]==ma[b])return 0;
if(fa[a]!=-1&&fa[a]==fa[b])return 0;
cnt++;
if(cnt>=4)
{
return 1;
}
return dfs(fa[a],fa[b],cnt)&&dfs(ma[a],fa[b],cnt)&&dfs(ma[a],ma[b],cnt)&&dfs(fa[a],ma[b],cnt);
}
int main()
{
int n;
cin>>n;
memset(fa,-1,sizeof fa);
memset(ma,-1,sizeof ma);
for(int i=1; i<=n; i++)
{
int a,fa1,ma1;
char mm[3];
cin>>a>>mm>>fa1>>ma1;
if(mm[0]=='M')
{
sex[a] = 0;
}
else sex[a] = 1;
if(fa1!=-1)
{
sex[fa1] = 0;
fa[a] = fa1;
}
if(ma1!=-1)
{
sex[ma1] =1;
ma[a] = ma1;
}
}
int k;
cin>>k;
for(int i=1; i<=k; i++)
{
int aa,bb;
cin>>aa>>bb;
int f = dfs(aa,bb,0);
if(sex[aa]==sex[bb])printf("Never Mind\n");
else if(f)printf("Yes\n");
else printf("No\n");
}
return 0;
}
CODE2
#include<iostream>
#include<string.h>
#define MAX 100010
using namespace std;
int father[MAX],mother[MAX];
typedef struct Man
{
char sex;
int fa,mo;
};
Man man[MAX];
int Find(int a,int b,int num)
{
if(a == -1 || b == -1)
return 1;
if((mother[a] != -1 && mother[a] == mother[b]) || (father[a] != -1 && father[a] == father[b]))
return 0;
num++;
if(num >= 4)
return 1;
return (Find(mother[a],mother[b],num) && Find(mother[a],father[b],num) && Find(father[a],father[b],num) && Find(father[a],mother[b],num));
}
int main()
{
memset(father,-1,sizeof(father));
memset(mother,-1,sizeof(mother));
int n,m;
cin >> n;
for(int i = 0;i < n; i++)
{
int a;
cin >> a;
cin >> man[a].sex >> man[a].fa >> man[a].mo;
if(man[a].fa != -1)
{
father[a] = man[a].fa;
man[man[a].fa].sex = 'M';//父母的性别没有设置，需要手动设置
}
if(man[a].mo != -1)
{
mother[a] = man[a].mo;//父母的性别没有设置，需要手动设置
man[man[a].mo].sex = 'F';
}
if(man[a].fa == -1)
father[a] = -1;
if(man[a].mo == -1)
mother[a] = -1;
}
cin >> m;
for(int i = 0;i < m; i++)
{
int a,b;
cin >> a >> b;
if(man[a].sex == man[b].sex)
cout <<"Never Mind"<<endl;
else
{
int num = 0;
if(Find(a,b,num))
cout <<"Yes"<<endl;
else
cout <<"No"<<endl;
}
}
return 0;
}