ZeroJudge 解題筆記：k849. P3.骨牌 (Domino)

作者：王一哲
日期：2025年5月8日



ZeroJudge 題目連結：k849. P3.骨牌 (Domino)

解題想法

這題是有向圖，我用集合 child 儲存子節點編號，用字典 nxt 儲存每個節點的子節點編號，讀取 n 行資料存入 child 及 nxt，再掃瞄一輪找出根節點（第一張牌），最後用一個 while 迴圈第根節點開始掃過所有的節點並將節點編號存入串列 ans。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # n 組資料，n 張牌
    child = set()  # 不是第一張牌的編號
    nxt = dict()  # 下一張牌的編號
    for _ in range(n):  # 讀取 n 行資料，u 的下一張是 v
        u, v = map(int, input().split())
        child.add(v)
        nxt[u] = v
    start = 0  # 第一張牌
    for u in nxt.keys():  # 從 nxt 的 keys 之中找第一張牌
        if u not in child:  # 只有一個 u 不在 child 之中
            start = u; break  # 找到就可以中止迴圈
    ans = [start]  # 先將 start 加入 ans
    while nxt[ans[-1]] != -1:  # 如果 ans 最後一項的下一張不是 -1 繼續執行
        ans.append(nxt[ans[-1]])  # 將找到的牌加入 ans
    print(*ans)

C++ 程式碼

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

#include <cstdio>
#include <map>
#include <set>
#include <vector>
using namespace std;

int main() {
    int n;  // n 組資料，n 張牌
    while(scanf("%d", &n) != EOF) {
        set<int> child;  // 不是第一張牌的編號
        map<int, int> nxt;  // 下一張牌的編號
        for(int i=0; i<n; i++) {  // 讀取 n 行資料，u 的下一張是 v
            int u, v; scanf("%d %d", &u, &v);
            child.insert(v);
            nxt[u] = v;
        }
        int start = 0;  // 第一張牌
        for(auto it : nxt) {  // 從 nxt 的 keys 之中找第一張牌
            int u = it.first;
            if (child.count(u) != 1) {  // 只有一個 u 不在 child 之中
                start = u; break;  // 找到就可以中止迴圈
            }
        }
        vector<int> ans = {start};  // 先將 start 加入 ans
        while(nxt[ans.back()] != -1) {  // 如果 ans 最後一項的下一張不是 -1 繼續執行
            ans.push_back(nxt[ans.back()]);  // 將找到的牌加入 ans
        }
        for(int i=0; i<n; i++) {
            printf("%d", ans[i]);
            if (i == n-1) puts("");
            else printf(" ");
        }
    }
    return 0;
}