题解 | #找出直系亲属#

#include<iostream>
#include<map>
using namespace std;
typedef map<char, pair<char, char>> MyMap;
bool answer = false;
int ccnt = 0;
void solve(MyMap mp, char c, char p, int& ans) {
    //递归dfs搜索
    if (c == p) {
        answer = true;
        ccnt = ans;
        return;
    }
    else if (mp.find(c) == mp.end())
        return;
    char cur = mp[c].first;
    int cnt = ans + 1;
    solve(mp, cur, p, cnt);
    cur = mp[c].second;
    solve(mp, cur, p, cnt);
}
void Output(int ans,int tag) {
    //如果是长者关系
    if(tag == 1){
        if (ans == 1)
            cout << "parent" << endl;
        else if (ans == 2)
            cout << "grandparent" << endl;
        else {
            string str = "grandparent";
            for (int i = ans; i > 2; i--)
                str = "great-" + str;
            cout << str << endl;
        }
    }
    else{
        if (ans == 1)
            cout << "child" << endl;
        else if (ans == 2)
            cout << "grandchild" << endl;
        else {
            string str = "grandchild";
            for (int i = ans; i > 2; i--)
                str = "great-" + str;
            cout << str << endl;
        }
    }
}
int main()
{
    int n, m;
    string str;
    MyMap mp;
    while (cin >> n >> m) {
        for (int i = 0; i < n; ++i) {
            cin >> str;
            //存储父母与孩子的关系
            mp[str.at(0)].first = str.at(1);
            mp[str.at(0)].second = str.at(2);
        }
        //关系判断
        for (int i = 0, ans; i < m; ++i) {
            cin >> str;
            ans = 0;
            //由于存在不确定FA谁是长者，那么需要两次遍历
            solve(mp, str[0], str[1], ans);
            if (answer)
                Output(ccnt,0);
            else {
                ans = 0;
                solve(mp, str[1], str[0], ans);
                if (answer)
                    Output(ccnt,1);
                else
                    cout << "-" << endl;
            }
            answer = false;
            ccnt = 0;
        }
    }
}