ZeroJudge A584: 親等關係

題目敘述

每筆資料第一行有一個正整數N，接下來會有N行，每行有若干個字串，第一個字串代表這個人是其他人的爸爸。最後一行會有兩個字串，要求輸出這兩個人是幾等親。

範例輸入 #1

3

PAM BOB TOM PAT

BOB LIZ ANN

PAT JIM

LIZ TOM

範例輸出 #1

3

範例輸入 #2

2

BOB LIZ ANN

PAM BOB TOM

LIZ ANN

範例輸出 #2

2

解題思路

使用Map來存每個人他跟誰有關係，使用StringStream來切割字串，並且使用BFS來找每一次尋找人的起點。

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

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

map<string, vector<string>>MAP;
map<string, int>walk;
int counts = 0;

void BFS(vector<string>start, string target)
{
    if (start.size() == 0) return;
    vector<string>newStart;
    for (int i = 0; i<start.size(); i++)
    {
        if (start[i] == target) return;
        vector<string>v = MAP[start[i]];
        walk[start[i]] = 1;
        for (int j = 0; j<v.size(); j++)
        {
            if (walk[v[j]] == 0) newStart.push_back(v[j]);
        }
    }
    counts++;
    BFS(newStart, target);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    string tmp;
    getline(cin, tmp);
    for (int i = 0; i<N; i++)
    {
        string str;
        getline(cin, str);
        stringstream ss;
        ss.clear();
        ss<<str;
        bool first = true;
        string start;
        while (true)
        {
            string s;
            ss>>s;
            if (ss.fail()) break;
            if (first)
            {
                start = s;
                first = false;
            }
            else
            {
                MAP[start].push_back(s);
                MAP[s].push_back(start);
            }
        }
    }
    string a, b;
    cin >> a >> b;
    vector<string>v;
    v.push_back(a);
    BFS(v, b);
    cout << counts << "\n";
}