ZeroJudge 解題筆記：k862. 輩份比較

作者：王一哲
日期：2025年12月4日


ZeroJudge 題目連結：k862. 輩份比較

解題想法

我用字典儲存每個節點的父節點與子節點，存完圖之後再找出沒有父節點的節點名稱，這個節點就是根節點。接下來由兩個要比較輩份的節點出發，由下往上走到根節點，找出與根節點之間的距離。最後將兩個距離相減就是輩份差。

Python 程式碼

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

n = int(input())  # n 組關係
parent = dict()  # 父節點
child = dict()  # 子節點
for _ in range(n):  # 讀取 n 行資料
    a, b = input().split()  # a 是 b 的子節點
    if b not in child: child[b] = [a]  # 更新子節點
    else: child[b].append(a)
    if a not in parent: parent[a] = b  # 更新父節點
root = ""  # 根節點
for b in child.keys():  # 依序取出 child 的 key 值 b
    if b not in parent:  # 如果 b 沒有父節點
        root = b  # b 是根節點
        break
p, q = input().split()  # 如果 p 是晚輩輸出負值，如果 p 是長輩輸出正值，平輩輸出 0
dp, dq = 0, 0  # 從根節點往下算的距離
curr = p  # 目前的節點
while curr != root:  # 從 p 往上走到根節點
    dp += 1
    curr = parent[curr]
curr = q  # 目前的節點
while curr != root:  # 從 q 往上走到根節點
    dq += 1
    curr = parent[curr]
print(dq - dp)  # 輸出答案

改用集合儲存子節點，使用時間約為 19 ms，記憶體約為 3.3 MB，通過測試。

n = int(input())  # n 組關係
parent = dict()  # 父節點
have_child = set()  # 有子節點的節點
for _ in range(n):  # 讀取 n 行資料
    a, b = input().split()  # a 是 b 的子節點
    have_child.add(b)  # b 有子節點
    if a not in parent: parent[a] = b  # 更新父節點
root = ""  # 根節點
for b in have_child:  # 依序取出有子節點的節點 b
    if b not in parent:  # 如果 b 沒有父節點
        root = b  # b 是根節點
        break
p, q = input().split()  # 如果 p 是晚輩輸出負值，如果 p 是長輩輸出正值，平輩輸出 0
dp, dq = 0, 0  # 從根節點往下算的距離
curr = p  # 目前的節點
while curr != root:  # 從 p 往上走到根節點
    dp += 1
    curr = parent[curr]
curr = q  # 目前的節點
while curr != root:  # 從 q 往上走到根節點
    dq += 1
    curr = parent[curr]
print(dq - dp)  # 輸出答案

C++ 程式碼

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

#include <iostream>
#include <map>
#include <string>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;  // n 組關係
    map<string, string> parent;  // 父節點
    set<string> have_child;  // 有子節點的節點
    for(int i=0; i<n; i++) {  // 讀取 n 行資料
        string a, b; cin >> a >> b;  // a 是 b 的子節點
        have_child.insert(b);  // b 有子節點
        parent[a] = b;  // 更新父節點
    }
    string root;  // 根節點
    for(auto b : have_child) {  // 依序取出有子節點的節點 b
        if (parent[b].empty()) {  // 如果 b 沒有父節點
            root = b;  // b 是根節點
            break;
        }
    }
    string p, q; cin >> p >> q;  // 如果 p 是晚輩輸出負值，如果 p 是長輩輸出正值，平輩輸出 0
    int dp = 0, dq = 0;  // 從根節點往下算的距離
    string curr = p;  // 目前的節點
    while(curr != root) {  // 從 p 往上走到根節點
        dp++;
        curr = parent[curr];
    }
    curr = q;  // 目前的節點
    while(curr != root) {  // 從 q 往上走到根節點
        dq++;
        curr = parent[curr];
    }
    cout << dq - dp << "\n";  // 輸出答案
    return 0;
}