ZeroJudge K862: 輩份比較

題目敘述

每筆輸入第一行有一個正整數N，接下來會有N行，每行會有兩個用空白隔開的未含空格的字串a和b，代表a是b的小孩、b是a的父母。收完資料之後還有一行，這一行有兩個用空白隔開的未含空格的字串c和d，要求輸出c和d的輩份關係，如果老一輩就-1，如果晚一輩就+1，如果是同輩就是0。

範例輸入 #1

3

Jacob Isaac

Isaac Abraham

Ishmael Abraham

Jacob Ishmael

範例輸出 #1

-1

範例輸入 #2

3

A ABC

B ABC

C ABC

A C

範例輸出 #2

0

範例輸入 #3

4

me dad

dad grand-dad

son me

grand-son son

grand-dad grand-son

範例輸出 #3

4

解題思路

本題類似於樹狀圖的概念，可以創建一個struct，裡面存名字、長輩、和晚輩。然後再利用Map來將名字當成Key把這些struct存進來。最後再使用BFS的方式從要找的名字開始往上和往下找，要注意的是，需要再使用一個Map來紀錄目前這個名字是否有被走過了以免進行重複的運算。

解題程式碼如下 (僅供參考)：

#include <iostream>
#include <map>
#include <vector>
using namespace std;

struct node
{
    vector<node*>up;
    vector<node*>down;
    string name;
    int val = 0;
};

map<string, node*>MAP;
map<string, int>walk;
string start, target;
int ans;

void BFS(vector<string>start)
{
    if (start.size() == 0) return;
    vector<string>newStart;
    for (int i = 0; i<start.size(); i++)
    {
        string name = start[i];
        walk[name] = 1;
        if (name == target)
        {
            ans = MAP[name]->val;
            return;
        }
        if (MAP[name]->up.size() != 0)
        {
            for (int j = 0; j<MAP[name]->up.size(); j++)
            {
                string fn = MAP[name]->up[j]->name;
                if (walk[fn] == 0) {
                    MAP[fn]->val = MAP[name]->val - 1;
                    newStart.push_back(fn);
                }
            }
        }
        if (MAP[name]->down.size() != 0)
        {
            for (int j = 0; j<MAP[name]->down.size(); j++)
            {
                string fn = MAP[name]->down[j]->name;
                if (walk[fn] == 0) {
                    MAP[fn]->val = MAP[name]->val + 1;
                    newStart.push_back(fn);
                }
            }
        }
    }
    BFS(newStart);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i<N; i++)
    {
        string a, b;
        cin >> a >> b;
        if (MAP[a] == nullptr)
        {
            node* tmp = new node();
            tmp->name = a;
            MAP[a] = tmp;
        }
        if (MAP[b] == nullptr)
        {
            node* tmp = new node();
            tmp->name = b;
            MAP[b] = tmp;
        }
        MAP[a]->up.push_back(MAP[b]);
        MAP[b]->down.push_back(MAP[a]);
    }
    cin >> start >> target;
    vector<string>v;
    v.push_back(start);
    BFS(v);
    cout << ans << "\n";
}