d279. 00280 - Vertex
Tags :
Accepted rate : 199人/208人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-15 02:36

Content

請寫一個程弍,在一個有向圖中搜尋從某個起始節點無法到達的節點。

一個有向圖包含編號 1...n 的 n 個節點 (1 ≤ n ≤ 100) 及一系列的邊,p -> q 代表單向連接 p, q 兩節點。

p 可以到達 r,若存在一個 p -> r 的邊;或是存在一個節點 q 使得 p 可以到達 q 且 q 可以到達 r。

Input

輸入資料含有若干個有向圖及起始節點。

對於每個有向圖,第一行含有一個整數 n,代表圖中的節點數。

接下來的若干行,每行有一組整數。若該行僅含一個 0,代表該有向圖的結束。這一組整數代表一組具有共同起始節點的邊,其中的一個整數 i 代表起始節點,接下來的整數 j...k 代表 i -> j ... i -> k 等以 i 為起始節點的邊。每一行的整數最後會有一個 0。

每個有向圖之後還有一行的整數,第一個整數代表其後還有多少整數,其後的整數則是你的程式要查詢的起始節點。

接下來是下一個有向圖。當沒有下一個有向圖時,會有一個 0 單獨在一行。

Output
對於每個要查詢的起始節點,你要找出所有該節點無法到達的節點。將這些節點輸出於一行,第一個整數為節點的個數,其後為節點的編號。
Sample Input #1
3
1 2 0
2 2 0
3 1 2 0
0
2 1 2
0
Sample Output #1
2 1 3
2 1 3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
原題
Tags:
出處:
UVa280 [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」