题解 | 找出直系亲属

#include <iostream>
#include<vector>
using namespace std;
bool ok;
int direct(int x, int y, vector<int> v1) {//是否为直系亲属（ok），返回两者的相对层次差
    int a = x, b = y, count1 = 0, count2 = 0, count = 0;
    while (v1[a] != -1 && v1[a] != y) {
        a = v1[a];
        count1 += 1;
    }
    while (v1[b] != -1 && v1[b] != x) b = v1[b], count2 -= 1;
    if (v1[a] == y) {
        count = count1;
        ok = true;
    } else if (v1[b] == x) {
        count = count2;
        ok = true;
    } else ok = false;
    v1[b] = x;
    return count;
}
int main() {
    int n, m;
    while (cin >> n >> m) {
        string res = "";
        vector<int> v1(26, -1);
        for (int i = 0; i < n; i++) {
            string relation;
            cin >> relation;
            int x = relation[0] - 65, y = relation[1] - 65, z = relation[2] - 65;
            if (relation[1] == '-') {
                v1[z] = x;
            } else if (relation[2] == '-') {
                v1[y] = x;
            } else
                v1[y] = x, v1[z] = x;
        }
        for (int i = 0; i < m; i++) {
            res = "";
            string ques;
            cin >> ques;
            int rels = direct(ques[0] - 65, ques[1] - 65, v1);
            if (rels == 0) {//如果层次差的结果为0，则rels正负无法判断子父关系，于是采用手动判断
                if (v1[ques[0] - 65] == ques[1] - 65) rels = 1;
                else rels = -1;
            }
            else
            rels = (rels > 0 ? rels + 1 : rels - 1);
            if (ok) {
                if (rels >= 2) {
                    for (int i = 3; i <= rels; i++) {
                        res += "great-";
                    }
                    res += "grandparent";
                } else if (rels == 1) {
                    res = "parent";
                } else if (rels <= -2) {
                    for (int i = rels; i <= -3; i++) {
                        res += "great-";
                    }
                    res += "grandchild";
                } else if (rels == -1) {
                    res = "child";
                }
                cout << res << endl;
            } else cout << '-' << endl;
        }
        v1.clear();
    }
}
// 64 位输出请用 printf("%lld")

用并查集实现直系亲属的寻找，在寻找的基础上添加计数，根据问询关系（前一个是后一个的什么）对计数添加正负判断