题目1035：找出直系亲属

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：1309

解决：521

题目描述：

如果A，B是C的父母亲，则A，B是C的parent，C是A，B的child，如果A，B是C的（外）祖父，祖母，则A，B是C的grandparent，C是A，B的grandchild，如果A，B是C的（外）曾祖父，曾祖母，则A，B是C的great-grandparent，C是A，B的great-grandchild，之后再多一辈，则在关系上加一个great-。

输入：

输入包含多组测试用例,每组用例首先包含2个整数n（0<=n<=26）和m（0<m<50）, 分别表示有n个亲属关系和m个问题, 然后接下来是n行的形式如ABC的字符串，表示A的父母亲分别是B和C，如果A的父母亲信息不全，则用-代替，例如A-C,再然后是m行形式如FA的字符串,表示询问F和A的关系。

当n和m为0时结束输入。

输出：

如果询问的2个人是直系亲属，请按题目描述输出2者的关系，如果没有直系关系，请输出-。

具体含义和输出格式参见样例.

样例输入：

3 2ABCCDEEFGFABE0 0

样例输出：

great-grandparent-

来源：

MYCode

#include<iostream>

#include<cstring>

#include<cstdio>

using 

namespace std;

#define MAX 

110

int pre[

27];

int find(

int id1, 

int id2)

{

    

int  ct = 

0;

    

while(id1 != id2 && id1 != -

1)

    {

        id1 = pre[id1];

        ct++;

    }

    

if(id1 == id2)

        

return ct;

    

return 

0;

}

int main()

{

    

int n, m;

    

while(scanf(

"%d%d", &n, &m) != EOF)

    {

        

if(n == 

0 && m == 

0)

            

break;

        memset(pre, -

1, 

sizeof(pre));

        

char str[

3];

        

int i;

        

for(i = 

1; i <= n; i++)

        {

            scanf(

"%s", &str);

            

int a, b = -

1, c = -

1;

            a = str[

0] - 

'A';

            

if(str[

1] >= 

'A' && str[

1] <= 

'Z')

                b = str[

1] - 

'A';

            

if(str[

2] >= 

'A' && str[

2] <= 

'Z')

                c = str[

2] - 

'A';

            

if(b != -

1)

                pre[b] = a;

            

if(c != -

1)

                pre[c] = a;

        }

        

/*for(i=0;i<26;i++)

        cout<<pre[i]<<" ";

        cout<<endl;*/

        

for(i = 

1; i <= m; i++)

        {

            

char ch1, ch2;

            cin >> ch1 >> ch2;

            

int index1 = ch1 - 

'A';

            

int index2 = ch2 - 

'A';

            

bool flag = 

false;

            

int res1 = find(index2, index1);

            

//cout<<"res1="<<res1<<endl;

            

if(res1)

            {

                flag = 

true;

                

switch(res1)

                {

                

case 

1:

                    cout << 

"child" << endl;

                    

break;

                

case 

2:

                    cout << 

"grandchild" << endl;

                    

break;

                

default:

                    

for(

int k = res1; k >= 

3; k--)

                        cout << 

"great-";

                    cout << 

"grandchild" << endl;

                    

break;

                }

            }

            

else

            {

                

int res2 = find(index1, index2);

                

//cout<<"res2="<<res2<<endl;

                

if(res2)

                {

                    flag = 

true;

                    

switch(res2)

                    {

                    

case 

1:

                        cout << 

"parent" << endl;

                        

break;

                    

case 

2:

                        cout << 

"grandparent" << endl;

                        

break;

                    

default:

                        

for(

int k = res2; k >= 

3; k--)

                            cout << 

"great-";

                        cout << 

"grandparent" << endl;

                        

break;

                    }

                }

            }

            

if(!flag)

                cout << 

"-" << endl;

        }

    }

}

//status：accepted

根据题目给的数据构建一棵二叉树

比如 题目给出的数据可以构成下面的二叉树

  A

↙↘

BC

↙↘

D E

    ↙↘

   F     G

判断F和A是否具有直系关系

从F一直向上搜索

F到E到C到A

找到了A说明F和A具有直属关系。

否则不具有直属关系。