题解 | #找出直系亲属#
找出直系亲属
https://www.nowcoder.com/practice/2c958d09d29f46798696f15ae7c9703b
/* 人还挺无语的,就这也叫困难题,难度划分一点也不靠谱。这道题甚至一点难的算法思想和复杂数据结构都没用到 一开始脑瓜子嗡嗡的,不知道怎么下手,看了部分题解,感觉有的人的方法非常清晰易懂就选用了 首先这题最小的儿子作为根节点,辈份越大,高度越低,深度越小 按照输入记录每个结点的儿子和深度 然后对m组关系: 若深度高的结点能顺着自己的儿子结点找到深度低的结点,这两人就有直系关系,否则无 */ #include<iostream> #include <cstring> using namespace std; int son[30]; int depth[30]; void Initial() { for(int i=0;i<30;i++) { son[i]=i; depth[i]=0; } } int Find(int p,int c,int k)//高深度结点,低深度,相差辈分数 { if(p==c)return k;//有直系关系 if(depth[p]==depth[c]&&p!=c)return -1;//没有直系关系 return Find(son[p],c,k+1); } int main() { int n,m; while(cin>>n>>m){ Initial(); for(int i=1;i<=n;i++) { string str;cin>>str; if(str[1]!='-') { son[str[1]-'A']=str[0]-'A'; depth[str[1]-'A']=1+depth[str[0]-'A']; } if(str[2]!='-') { son[str[2]-'A']=str[0]-'A'; depth[str[2]-'A']=1+depth[str[0]-'A']; } } for(int i=1;i<=m;i++) { string str;cin>>str; if(depth[str[0]-'A']>depth[str[1]-'A'])//输出parent关系 { int k=Find(str[0]-'A',str[1]-'A',0);//找奶奶和孙子相差几辈 //cout<<k;// if(k==-1)cout<<"-"<<endl; else if(k==1)cout<<"parent"<<endl; else if(k==2)cout<<"grandparent"<<endl; else { int l=k-2; for(int j=1;j<=l;j++) cout<<"great-"; cout<<"grandparent"<<endl; } } else if(depth[str[0]-'A']<depth[str[1]-'A'])//输出child关系 { int k=Find(str[1]-'A',str[0]-'A',0);//找孙子和奶奶相差几辈 if(k==-1)cout<<"-"<<endl; else if(k==1)cout<<"child"<<endl; else if(k==2)cout<<"grandchild"<<endl; else { int l=k-2; for(int j=1;j<=l;j++) cout<<"great-"; cout<<"grandchild"<<endl; } } else {//在同层肯定没有直系亲属关系 //cout<<"同深度";// cout<<"-"<<endl; } } } }