题解 | #找出直系亲属#

并查集

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
void Union(vector<int>& s, int a, int b) {       //ABC 将A看作B和C的父结点
    s[b] = a;
}

int Find(vector<int>& s, int a, int b) {
    int cnt = 0;
    while (s[a] >= 0) {
        cnt++;
        if (s[a] == b) return cnt;
        a = s[a];
    }
    return 0;
}

int main()       //整个数据结构像翻转过来的二叉树
{
    int n, m;
    cin >> n;
    cin >> m;
    vector<int> s(26, -1);
    getchar();
    while (n--) {
        string str;
        getline(cin, str);
        if (str[1] != '-') Union(s, str[0] - 'A', str[1] - 'A');
        if (str[2] != '-') Union(s, str[0] - 'A', str[2] - 'A');        
    }
    while (m--) {
        string str;
        getline(cin, str);
        int cnt1 = Find(s, str[0] - 'A', str[1] - 'A');
        if (cnt1 > 0) {
            if (cnt1 == 1) {
                cout << "parent" << endl;
                continue;
            }
            if (cnt1 == 2) {
                cout << "grandparent" << endl;
                continue;
            }
            string res = "grandparent";
            cnt1 = cnt1 - 2;
            while (cnt1--) {
                res = "great-" + res;
            }
            cout << res << endl;
            continue;
        }
        int cnt2 = Find(s, str[1] - 'A', str[0] - 'A');
        if (cnt2 > 0) {
            if (cnt2 == 1) {
                cout << "child" << endl;
                continue;
            }
            if (cnt2 == 2) {
                cout << "grandchild" << endl;
                continue;
            }
            string res = "grandchild";
            cnt2 = cnt2 - 2;
            while (cnt2--) {
                res = "great-" + res;
            }
            cout << res << endl;
            continue;
        }
        if (cnt1 == 0 && cnt2 == 0) cout << "-" << endl;
    }
    return 0;
}