题目描述：

    如果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-

http://ac.jobdu.com/problem.php?pid=1035

 1 #include <iostream> 2 #define NUMSIZE 26 3 using namespace std; 4  5 int get_num(char a); 6 void build_tree(int tree[], int n); 7 void printf_relation(int tree[], int m); 8 int get_generation(int tree[], int a, int b); 9 void print(int gene,string relation);10 11 int main()12 {13     int n,m;14     int tree[NUMSIZE];15     for(int i=0; i<NUMSIZE; i++)16         tree[i] = -1;17     int t[3]={-1};18     char c;19     while(cin>>n && n>0) {20         cin>>m;21         build_tree(tree, n);22         printf_relation(tree, m);23     }24     return 0;25 }26 int get_num(char a) {27     if(a==‘-‘)28         return -1;29     return a-‘A‘;30 }31 void build_tree(int tree[], int n) {32     int t[3]={-1};33     char c;34     for(int i=0; i<n; i++) {35         for(int j=0; j<3; j++) {36             cin>>c;37             t[j]=get_num(c);38         }39         if(tree[t[0]] == -1)40             tree[t[0]] = t[0];41         if(t[1]!=-1)42             tree[t[1]] = t[0];43         if(t[2]!=-1)44             tree[t[2]] = t[0];45     }46 }47 void printf_relation(int tree[], int m) {48     int t[2] = {-1};49     char a,b;50     for(int i=0; i<m; i++) {51         int generation;52         cin>>a>>b;53         t[0]=get_num(a);54         t[1]=get_num(b);55         if((generation=get_generation(tree, t[0], t[1])) !=0)56             print(generation,"parent");57         else if((generation=get_generation(tree, t[1], t[0])) !=0)58             print(generation,"child");59         else60             cout<<"-"<<endl;61     }62 }63 int get_generation(int tree[], int a, int b) {64     int num=0;65     while(a!=tree[a]){66         if(tree[a] == b)67             return ++num;68         a=tree[a];69         ++num;70     }71     return 0;72 }73 void print(int gene, string relation) {74     switch(gene) {75         case 1: cout<<relation<<endl;76                 break;77         case 2: cout<<"grand"<<relation<<endl;78                 break;79         default:80             for(int i=0; i<gene-2; i++)81                 cout<<"great-";82             cout<<"grand"<<relation<<endl;83     }84 }

main.cpp

 

ACM&找双亲，并查集