九度OJ 1035:找出直系亲属(二叉树)

题目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 2
ABC
CDE
EFG
FA
BE
0 0

样例输出：

great-grandparent
-

来源：

2009年浙江大学计算机及软件工程研究生机试真题

MYCode

#include<iostream> #include<cstring> #include<cstdio> using  namespace std; #define MAX int pre[ ]; int find( int id1,  int id2) {      int  ct =  ;      while(id1 != id2 && id1 != - )     {         id1 = pre[id1];         ct++;     }      if(id1 == id2)          return ct;      return  ; } int main() {      int n, m;      while(scanf( "%d%d", &n, &m) != EOF)     {          if(n ==   && m ==  )              break;         memset(pre, - ,  sizeof(pre));          char str[ ];          int i;          for(i =  ; i <= n; i++)         {             scanf( "%s", &str);              int a, b = - , c = - ;             a = str[ ] -  'A';              if(str[ ] >=  'A' && str[ ] <=  'Z')                 b = str[ ] -  'A';              if(str[ ] >=  'A' && str[ ] <=  'Z')                 c = str[ ] -  'A';              if(b != - )                 pre[b] = a;              if(c != - )                 pre[c] = a;         }          /*for(i=0;i<26;i++)         cout<<pre[i]<<" ";         cout<<endl;*/          for(i =  ; 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  :                     cout <<  "child" << endl;                      break;                  case  :                     cout <<  "grandchild" << endl;                      break;                  default:                      for( int k = res1; k >=  ; k--)                         cout <<  "great-";                     cout <<  "grandchild" << endl;                      break;                 }             }              else             {                  int res2 = find(index1, index2);                  //cout<<"res2="<<res2<<endl;                  if(res2)                 {                     flag =  true;                      switch(res2)                     {                      case  :                         cout <<  "parent" << endl;                          break;                      case  :                         cout <<  "grandparent" << endl;                          break;                      default:                          for( int k = res2; k >=  ; 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具有直属关系。

否则不具有直属关系。