ZeroJudge 解題筆記：a584. 2. 親等關係

作者：王一哲
日期：2025年11月21日


ZeroJudge 題目連結：a584. 2. 親等關係

解題想法

題目看起來像是樹，但其實用字典及串列儲存無向圖，再用 BFS 找兩個人之間的距離就過關了。如果用 Python 解題可以用 collections.defaultdict 存圖，這樣可以不需要檢查 key 值是否已在字典之中。我用 Python 寫這題很順利，反而是用 C++ 解題是吃了好幾次 WA，後來發現測資在第 1 行的人數 n 之後換行的格式可能比較特別，我一開始只有 cin.ignore() 跳過一個 \n，但是這樣會吃 WA，改成用 getline 讀取一整行才過關。

Python 程式碼

使用時間約為 16 ms，記憶體約為 3.3 MB，通過測試。

from collections import defaultdict, deque

""" 讀取測資並存圖 """
n = int(input())  # n 個人
graph = defaultdict(list)  # 無向圖，用字串當作 key，list 裡面存字串
for _ in range(n):  # 讀取 n 行
    names = input().split()  # 名字，用空格分割
    parent = names[0]  # 父節點名稱
    children = names[1:]  # 子節點名稱，可能有多個子節點
    for child in children:  # 依序讀取每個子節點名稱
        graph[parent].append(child)  # 儲存節點之間連接的方式
        graph[child].append(parent)
""" 讀取最後一行並用 BFS 找答案 """
a, b = input().split()  # 要找距離的兩個人名
que = deque([(a, 0)])  # 待走訪佇列，資料為 (節點, 距離)，先存入 (a, 0)
ans = 0  # 答案
visited = {a}  # 用 set 儲存已走訪節點名稱
while que:  # 如果 que 有資料繼續執行
    u, d = que.popleft()  # 從 que 開頭取出節點 u、距離 d
    if u == b:  # 如果 u 等於 b，找到終點
        ans = d  # 答案為 d
        break  # 中止迴圈
    for v in graph[u]:  # 依序讀取與 u 相連的節點 v
       if v in visited: continue  # 如果 v 已走訪過，找下一個節點
       visited.add(v)  # v 加入 visited
       que.append((v, d+1))  # (v, d+1) 加入 que
# 結束 BFS，印出答案
print(ans)

C++ 程式碼

使用時間約為 3 ms，記憶體約為 344 kB，通過測試。

#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <vector>
#include <queue>
#include <utility>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    /* 讀取測資並存圖 */
    int n; cin >> n;  // n 個人
    string tmp;
    getline(cin, tmp);  // 清除第一個 \n
    map<string, vector<string>> graph;  // 無向圖，用字串當作 key，vector 裡面存字串    
    for(int i=0; i<n; i++) {  // 讀取 n 行
        string s;  // 暫存一行資料用的字串
        getline(cin, s);  // 讀取一整行
        stringstream ss (s);  // 暫存分割後的字串用的容器
        string parent, child;  // 父節點、子節點名稱
        ss >> parent;
        while(ss >> child) {  // 依序讀取每個子節點名稱
            graph[parent].push_back(child);  // 儲存節點之間連接的方式
            graph[child].push_back(parent);
        }
    }
    /* 讀取最後一行並用 BFS 找答案 */
    string a, b; cin >> a >> b;  // 要找距離的兩個人名
    queue<pair<string, int>> que;  // 待走訪佇列，資料為 (節點, 距離)
    que.push(make_pair(a, 0));  // 先存入 (a, 0)
    int ans = -1;  // 答案
    set<string> visited = {a};  // 用 set 儲存已走訪節點名稱
    while(!que.empty()) {  // 如果 que 有資料繼續執行
        string u = que.front().first;  // 從 que 開頭取出節點 u、距離 d
        int d = que.front().second;
        que.pop();
        if (u == b) {  // 如果 u 等於 b，找到終點
            ans = d;  // 答案為 d
            break;  // 中止迴圈
        }
        for(string v : graph[u]) {  // 依序讀取與 u 相連的節點 v
            if (visited.count(v) == 1) continue;  // 如果 v 已走訪過，找下一個節點
            visited.insert(v);  // v 加入 visited
            que.push(make_pair(v, d+1));  // (v, d+1) 加入 que
        }
    }
    // 結束 BFS，印出答案
    cout << ans << "\n";
    return 0;
}