题解 | #找出直系亲属#

找出直系亲属

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;
            }
        }

        
    }
}



全部评论

相关推荐

11-26 22:34
已编辑
重庆邮电大学 Java
快手 客户端开发 (n+5)k*16 公积金12
牛客895077908号:佬 什么双非硕啊
点赞 评论 收藏
分享
有工作后先养猫:太好了,是超时空战警,我们有救了😋
点赞 评论 收藏
分享
11-03 14:38
重庆大学 Java
AAA求offer教程:我手都抬起来了又揣裤兜了
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务