九度 OJ 1035 找出直系親屬：樹構造 + 祖先查找輸出關系稱謂

題目大意

給定 n（≤26）條親屬關係，格式 ABC 表示 A 的父母是 B、C（- 表示未知）。再給 m（<50）個查詢 FA，詢問 F 和 A 的直系關系。輸出關系稱謂：parent/child/grandparent/grandchild/great-grandparent... 若無直系關系輸出 -。

解題思路

1. 用 map 將人物映射為索引，建立父指針陣列 parent[idx]（每人最多兩父母，但題目只需任一父母鏈向上查找，因直系關系只需單邊）。
2. 對每個查詢 (X, Y)：
    - 從 X 向上找 Y，記錄步數 d1。
    - 從 Y 向上找 X，記錄步數 d2。
    - 若兩者都找不到 → -。
    - 若找到：
      d=1 → parent/child
   d=2 → grandparent/grandchild
   d≥3 → great- 重複 d-2 次 + grandparent/grandchild

代碼實現

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m;
    while (cin >> n >> m, n || m) {
        map id;
        vector parent(52, -1); // 最多 26 人，雙向存父母
        int cnt = 0;
        auto getId = [&](char c) {
            if (c == '-') return -1;
            if (!id.count(c)) id[c] = cnt++;
            return id[c];
        };
        for (int i = 0; i < n; ++i) {
            string s; cin >> s;
            int a = getId(s[0]), b = getId(s[1]), c = getId(s[2]);
            if (b != -1) parent[b] = a;
            if (c != -1) parent[c] = a;
        }
        auto findDist = [&](int from, int to) {
            int d = 0;
            while (from != -1 && from != to) { from = parent[from]; ++d; }
            return (from == to) ? d : -1;
        };
        for (int i = 0; i < m; ++i) {
            string q; cin >> q;
            int u = getId(q[0]), v = getId(q[1]);
            if (u == -1 || v == -1) { cout << "-\n"; continue; }
            int d1 = findDist(u, v);
            int d2 = findDist(v, u);
            if (d1 == -1 && d2 == -1) { cout << "-\n"; continue; }
            if (d1 != -1) { // u 是 v 的祖先
                if (d1 == 1) cout << "parent\n";
                else if (d1 == 2) cout << "grandparent\n";
                else { for (int k = 0; k < d1-2; ++k) cout << "great-"; cout << "grandparent\n"; }
            } else { // v 是 u 的祖先
                if (d2 == 1) cout << "child\n";
                else if (d2 == 2) cout << "grandchild\n";
                else { for (int k = 0; k < d2-2; ++k) cout << "great-"; cout << "grandchild\n"; }
            }
        }
    }
    return 0;
}

關鍵點

• 親屬關係構建的是森林（每人最多兩父母，但向上查找只需一條鏈）。
• 查詢時雙向查找，確定祖先/後代方向。
• 稱謂生成規則嚴格遵循題目描述。

複雜度

• 構建：O(n)。
• 每查詢：O(深度) ≤ O(n)，總 O(m n)，極小。