题解 | #找出直系亲属#

/*
人还挺无语的，就这也叫困难题，难度划分一点也不靠谱。这道题甚至一点难的算法思想和复杂数据结构都没用到

一开始脑瓜子嗡嗡的，不知道怎么下手，看了部分题解，感觉有的人的方法非常清晰易懂就选用了

首先这题最小的儿子作为根节点，辈份越大，高度越低，深度越小

按照输入记录每个结点的儿子和深度

然后对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;
            }
        }

        
    }
}