题解 | #找出直系亲属#

#include<cstdio>
#include<iostream>
#include<utility>
#include<map>
// 采用并查集思想，用son数组记录自己儿子结点

using namespace std;

const int MAXN = 51;
int son[MAXN];
int height[MAXN];

void initial(){
    for(int i=0;i<MAXN;++i)
        son[i] = i;
}

int find(int x, int y) {
    int ans = 0;
    while(son[x] != x){
        if(son[x] == y) {
            ++ans;
            break;
        }
        else {
            ++ans;
            x = son[x];
        }
    }
    if(son[x] == x)
        return 0;
    return ans;
}

int main(){
    initial();
    int n,m;
    scanf("%d %d\n", &n, &m);
    char a,b,c;
    while(n--){
        scanf("%c%c%c\n", &a, &b, &c);
        son[b-'A'] = a-'A';
        son[c-'A'] = a-'A';
    }
    while(m--) {
        scanf("%c%c\n", &a, &b);
//         a 是 b 的什么？
        int ans = find(a-'A', b-'A');
        // 如果ans==0，那么说明a不是b的祖先。
        if(ans == 0) {
            ans = find(b-'A', a-'A');
            // ans == 0，说明b也不是a的祖先。说明二者没关系。
            if(ans == 0) {
                printf("-\n");
            }else{
                if(ans==1)
                    printf("child\n");
                else if(ans >= 2) {
                    for(int i=0;i<ans-2;++i)
                        printf("great-");
                    printf("grandchild\n");
                }
            }
        }
        else {
            if(ans == 1) 
                printf("parent\n");
            else if(ans >= 2) {
                for(int i=0;i<ans-2;++i)
                    printf("great-");
                printf("grandparent\n");
            }
        }
    }
    
    return 0;
}