日期：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)
