贝壳2018.9.3笔试题之家族关系
思路：时间紧张 什么图啊 树啊 都觉得不好实现 用map最简单了 把所有已知的信息先存入map 存入的时候（1）确定根 谁和根比较都是根的孩子 （2）兄弟关系，如果a b 的祖先相同，那么肯定是兄弟 （3）祖先关系 可能不是直系需要while循环判断 （4）如果都判断完毕不是祖先，那么肯定是没关系
代码如下：ac38% 不知道哪种自己没考虑到~欢迎大佬指出！
#include<iostream>
#include<map>
using namespace std;
int main()
{
int n;
cin>>n;
map<int,int>zupu;
int root=0;
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
pair<int,int>value(a,b);
zupu.insert(value);
if(zupu[a]==-1)
root=a;
}
int m;
cin>>m;
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
if(a==root||zupu[b]==a)
{
cout<<"1"<<endl;
}
else if(b==root||zupu[a]==b)
{
cout<<"2"<<endl;
}
else if(zupu[a]==zupu[b])
{
cout<<"0"<<endl;
}
else
{
bool flag=true;
int tmp1;
while(zupu.find(zupu[b])!=zupu.end())
{
tmp1=zupu[b];
if(zupu[tmp1]==a)
{
cout<<"1"<<endl;
flag=false;
break;
}
b=tmp1;
}
int tmp;
while(flag&&zupu.find(zupu[b])!=zupu.end())
{
tmp=zupu[b];
if(zupu[tmp]==a)
{
cout<<"1"<<endl;
flag=false;
break;
}
b=tmp;
}
if(flag)
cout<<"0"<<endl;
}
}
return 0;
}
#贝壳找房#
快手公司福利 222人发布
