找出直系亲属

前言


学java有点辛苦，主要还是有点抵触，对c、php、python有兴趣，而且java好庞大，学深了也不容易，唉，做到acm题目缓缓


题目


[plain] view plaincopy
题目描述：  
    如果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     当n和m为0时结束输入。  
输出：  
    如果询问的2个人是直系亲属，请按题目描述输出2者的关系，如果没有直系关系，请输出-。  
    具体含义和输出格式参见样例.  
样例输入：  
3 2  
ABC  
CDE  
EFG  
FA  
BE  
0 0  




思路


其实就是并查集的简单应用，因为外祖父和祖父可以当成一类来考虑，无疑降低了这到题目的难度，所以让并查集parent[x]的值为他的孩子即可




AC代码


[cpp] view plaincopy
#include  
#include  
   
#define N 26  
   
int parent[N];  
   
void preProcess()  
{  
    int i;  
   
    for (i = 0; i < N; i ++) {  
        parent[i] = i;  
    }  
}  
   
int findSet(int x, int y)  
{  
    int rel = 0;  
   
    while (x != y && parent[x] != x) {  
        rel ++;  
        x = parent[x];  
    }  
       
    if (x == y) {  
        return rel;  
    } else {  
        return 0;  
    }  
}  
   
int main(void)  
{  
    int m, n, i, j, rel;  
    char str[3], query[2];  
   
    while (scanf("%d %d", &n, &m) != EOF) {  
        if (n == 0 && m == 0)   break;  
   
        preProcess();  
   
        // 构造并查集  
        for (i = 0; i < n; i ++) {  
            scanf("%s", str);  
            for (j = 1; j < 3; j ++) {  
                if (str[j] != '-') {  
                    parent[str[j] - 'A'] = str[0] - 'A';  
                }  
            }  
        }  
   
        for (i = 0; i < m; i ++) {         
            scanf("%s", query);  
           
            rel = findSet(query[0] - 'A', query[1] - 'A');                
               
            if (rel) {  
                switch (rel) {  
                    case 1 :  
                        printf("parent\n");  
                        break;  
                    case 2 :  
                        printf("grandparent\n");  
                        break;  
                    default :  
                        for (j = rel - 2; j > 0; j --) {  
                            printf("great-");  
                        }  
                        printf("grandparent\n");  
                        break;  
                }  
            } else {  
                rel = findSet(query[1] - 'A', query[0] - 'A');  
                switch (rel) {  
                    case 0 :  
                        printf("-\n");  
                        break;  
                    case 1 :  
                        printf("child\n");  
                        break;  
                    case 2 :  
                        printf("grandchild\n");  
                        break;  
                    default :  
                        for (j = rel - 2; j > 0; j --) {  
                            printf("great-");  
                        }  
                        printf("grandchild\n");  
                        break;  
                }  
            }  
        }  
    }  
   
    return 0;  
}