ZeroJudge 解題筆記：c131. 00615 - Is It A Tree?

作者：王一哲
日期：2026年3月23日


ZeroJudge 題目連結：c131. 00615 - Is It A Tree?

解題想法

用自訂函式 test 代入節點資料，檢測是否為樹。檢測項目為

• 讀取邊的端點 $u, v$，因為 $u$ 可以連到 $v$，$u$ 為父節點，$v$ 為子節點。如果 $v$ 已經有父節點，因為一個節點不可能有兩個父節點，不是樹，回傳 False。
• 檢查是否只有一個根節點，因為不可能有兩個根節點。
• 用 BFS 從根節點開始走訪，如果能夠走到所有節點，是樹，回傳 True。

Python 程式碼

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

import sys
from collections import deque

def test(data):  # 檢測用的函式，輸入節點資料
    if data == [0, 0]: return True  # 特例，資料只有 0, 0，回傳 True
    parent, children = dict(), dict()  # {v: u} v 的父節點是 u，u 的子節點集合
    nodes = set()  # 所有節點的集合
    for i in range(0, len(data), 2):  # 一次讀取兩筆測資
        u, v = data[i], data[i+1]  # 節點 u 連到 v
        nodes.add(u); nodes.add(v)  # u, v 加入 nodes
        if v in parent: return False  # 如果 v 已經有父節點，回傳 True
        parent[v] = u  # v 的父節點是 u
        if u not in children: children[u] = {v}  # 如果 u 還沒有子節點，建立集合，加入 v
        else: children[u].add(v)  # 反之，直接加入 v
    ### 檢查是否只有一個根節點 ###
    root = -1  # 根節點
    for node in nodes:  # 依序讀取所有節點
        if node not in parent:  # 如果 node 沒有父節點
            if root == -1: root = node  # 如果 root 等於 -1，node 是根節點
            elif root != -1: return False  # 反之，不可能有兩個根節點，回傳 False
    ### BFS 檢查所有節點是否相連 ###
    que = deque([root])  # 待走訪佇列，先加入根節點
    visited = {node: False for node in nodes}  # 各節點走訪狀態
    visited[root] = True  # 已走訪根㿝3點
    while que:  # 如果 que 還有資料繼續執行
        u = que.popleft()  # 從 que 開頭取出資料
        if u not in children: continue  # 如果 u 沒有子節點，找下一個點
        for v in children[u]:  # 依序讀取 u 的子節點 v
            if visited[v]: return False  # 如果 v 已走訪，環狀結構，回傳 False
            visited[v] = True  # 已走訪 v
            que.append(v)  # v 加入 que
    ### End of BFS，如果所有節點已走訪回傳 True ###
    return all(visited.values())

"""" 讀取資料並解題 """
lines = sys.stdin.readlines()  # 讀取所有測資
idx = 0  # 從 lines 讀取資料的索引值
ca = 0  # 第幾組測資
result = []  # 要輸出的字串
while idx < len(lines):  # 如果 idx 還沒有出界繼續執行
    line = lines[idx]  # 讀取一行
    idx += 1
    line = line.strip()  # 跳過空行
    if not line: continue
    if line == "-1 -1": break  # 中止迴圈的條件
    ca += 1
    if line == "0 0":  # 特例，這組測資只有 0 0
        data = [0, 0]
    else:  # 其它狀況
        data = list(map(int, line.split()))  # 轉成整數串列
        if data[-1] == 0 and data[-2] == 0:  # 如果最後兩項都是 0
            data = data[:-2]  # 去掉最後兩項，結束這組測資
        else:  # 還有測資
            while True:  # 繼續讀取，直到結尾是 0 0 為止
                tmp = list(map(int, lines[idx].split()))
                idx += 1
                if tmp[-1] == 0 and tmp[-2] == 0:
                    data += tmp[:-2]
                    break
                else: data += tmp
    state = " " if test(data) else " not "  # 依照測試結果決定輸出的內容
    result.append(f"Case {ca:d} is{state:s}a tree.\n")
sys.stdout.write("".join(result))

C++ 程式碼

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

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

bool test(vector<int>& data) {  // 檢測用的函式，輸入節點資料
    map<int, int> parent;  // {v: u} v 的父節點是 u
    map<int, set<int>> children;  // u 的子節點集合
    set<int> nodes;  // 所有節點的集合
    for(int i=0; i<(int)data.size(); i+=2) {  // 一次讀取兩筆資料
        int u = data[i], v = data[i+1];  // 節點 u 連到 v
        nodes.insert(u); nodes.insert(v);  // u, v 加入 nodes
        if (parent.find(v) != parent.end()) return false;  // 如果 v 已經有父節點，回傳 True
        parent[v] = u;  // v 的父節點是 u
        children[u].insert(v);  // 如果 u 的子節點加入 v
    }
    /* 檢查是否只有一個根節點 */
    int root = -1;  // 根節點
    for(int node : nodes) {  // 依序讀取所有節點
        if (parent.find(node) == parent.end()) {  // 如果 node 沒有父節點
            if (root == -1) root = node;  // 如果 root 等於 -1，node 是根節點
            else if (root != -1) return false;  // 反之，不可能有兩個根節點，回傳 False
        }
    }
    /* BFS 檢查所有節點是否相連 */
    queue<int> que; que.push(root);  // 待走訪佇列，先加入根節點
    map<int, bool> visited;  // 各節點走訪狀態
    for(int node : nodes) visited[node] = false;
    visited[root] = true;  // 已走訪根節點
    while(!que.empty()) {  // 如果 que 還有資料繼續執行
        int u = que.front(); que.pop();  // 從 que 開頭取出資料
        if (children[u].empty()) continue;  // 如果 u 沒有子節點，找下一個點
        for(int v : children[u]) {  // 依序讀取 u 的子節點 v
            if (visited[v]) return false;  // 如果 v 已走訪，環狀結構，回傳 False
            visited[v] = true;  // 已走訪 v
            que.push(v);  // v 加入 que
        }
    }
    /* End of BFS，如果任意一個節點還沒有走訪，回傳 frue */
    for(auto it : visited) {
        if (!(it.second)) return false;
    }
    return true;
}

/* 讀取資料並解題 */
int main() {
    int ca = 0, u, v;  // 第幾組測資，節點 u, v
    while(scanf("%d %d", &u, &v) != EOF && (u != -1 || v != -1)) {
        ca++;
        vector<int> data;  // 測資
        bool state = true, empty = false;  // 是否是樹，樹是否是空的
        if (u == 0 && v == 0) {
            state = true;
            empty = true;
        } else {
            data.push_back(u);
            data.push_back(v);
            while(scanf("%d %d", &u, &v) != EOF && (u != 0 || v != 0)) {
                data.push_back(u);
                data.push_back(v);
            }
        }
        if (!empty) state = test(data);
        /* 依照測試結果決定輸出的內容 */
        if (state) printf("Case %d is a tree.\n", ca);
        else printf("Case %d is not a tree.\n", ca);
    }
    return 0;
}