ZeroJudge 解題筆記：d279. 00280 - Vertex

作者：王一哲
日期：2026年5月28日


ZeroJudge 題目連結：d279. 00280 - Vertex

解題想法

這題有兩個奇怪的地方。 第一個是起點不算可以走到的點，例如範例測資的圖，節點1可以到節點2，節點2只能走到節點2，節點3可以走到節點1、2；輸出節點1無法走到的節點數量及編號才會是 2 1 3。 第二個是實際測資與中文的題目敘述不合，但其實是中文翻譯錯誤，多張圖之間沒有用一行單獨的 0 分隔，只有在全部的測資都結束後才會有一行單獨的 0。英文版題目在此，原題敘述是

If there are no more graphs, the next line of the file will contain only the integer ‘0’.

Python 程式碼

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

import sys

result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    """ 讀取測資，建立圖的關係 """
    graph = [[] for _ in range(n+1)]
    for row in sys.stdin:
        if row.strip() == "0": break
        arr = list(map(int, row.split()))
        u = arr[0]
        for v in arr[1:-1]:
            graph[u].append(v)
    """ 讀取要檢查的起點 """
    data = list(map(int, sys.stdin.readline().split()))
    m = data[0]  # 起點數量，用不到
    for start in data[1:]:  # 依序測試每一個起點，用 BFS 找連通的節點
        que = [start]
        head = 0
        visited = [False]*(n+1)
        while head < len(que):
            u = que[head]
            head += 1
            for v in graph[u]:
                if visited[v]: continue
                visited[v] = True
                que.append(v)
        ### End of BFS ###
        ans = [i for i in range(1, n+1) if not visited[i]]  # 無法走到的節點
        result.append(f"{len(ans):d} " + " ".join(map(str, ans)) + "\n")
sys.stdout.write("".join(result))

C++ 程式碼

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

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

int main() {
    int n;
    while(scanf("%d", &n) != EOF && n != 0) {
        /* 讀取測資，建立圖的關係 */
        vector<vector<int>> graph (n+1);
        int u;
        while(scanf("%d", &u) != EOF && u != 0) {
            int v;
            while(scanf("%d", &v) != EOF && v != 0) {
                graph[u].push_back(v);
            }
        }
        /* 讀取要檢查的起點 */
        int m, start; scanf("%d", &m);  // 起點數量、起點編號
        for(int i=0; i<m; i++) {  // 依序測試每一個起點，用 BFS 找連通的節點
            scanf("%d", &start);
            queue<int> que;
            que.push(start);
            vector<bool> visited (n+1, false);
            while(!que.empty()) {
                int a = que.front();
                que.pop();
                for(int b : graph[a]) {
                    if (visited[b]) continue;
                    visited[b] = true;
                    que.push(b);
                }
            }
            // End of BFS
            vector<int> ans;  // 無法走到的節點
            for(int j=1; j<=n; j++) {
                if (!visited[j]) ans.push_back(j);
            }
            printf("%lu", ans.size());
            for(int it : ans) printf(" %d", it);
            puts("");
        }
    }
    return 0;
}