题解 | 找出直系亲属

#include<iostream>

using namespace std;
int f[26];
void init() {
    for (int i = 0; i < 50; i++) {
        f[i] = i;
    }
}
int find(int x) {
    if (x != f[x])return find(f[x]);
    return f[x];
}

int main() {
    int n, m;
    cin >> n >> m;
    string s;
    init();
    while (n--) {
        cin >> s;
        int a = s[0] - 'A';
        for (int i = 1; i < s.size(); i++) {
            if (s[i] == '-')continue;
            int t = s[i] - 'A';
            f[t] =  a;
        }
    }
    while (m--) {
        cin >> s;
        int a = s[0] - 'A', b = s[1] - 'A';
        int num = 0;
        int pl = a, ul = b; //先测试a为祖先，a——>b关系
        while (b != f[pl]) {
            if (pl == f[pl])break;
            pl = f[pl];
            num++;
        }
        if (b == f[pl]) { //a找到了b，b是a的后代
            num++;
            string str = "parent";
            if (num == 1)str = "parent";
            else if (num == 2)str = "grandparent";
            else {
                str = "grandparent";
                while (num != 2) {
                    str = "great-" + str;
                    num--;
                }
            }
            cout << str << endl;
        } else if (b != f[pl]) { //说明b在a前,b为a的祖先
            num = 0;
            while (a != f[ul]) {
                if (ul == f[ul])break;
                ul = f[ul];
                num++;
            }
            if (a == f[ul]) {
                num++;
                string str = "child";
                if (num == 1)str = "child";
                else if (num == 2)str = "grandchild";
                else {
                    str = "grandchild";
                    while (num != 2) {
                        str = "great-" + str;
                        num--;
                    }
                }
                cout << str << endl;
            }
        }
        if (b != f[pl] && a != f[ul]) {
            cout << "-" << endl;
            continue;
        }

    }
}