切換
舊版
前往
大廳
主題

ZeroJudge - d279: 00280 - Vertex 解題心得

Not In My Back Yard | 2020-09-04 00:00:38 | 巴幣 0 | 人氣 157

題目連結:


題目大意:
輸入有多筆測試資料。每筆第一列給定一正整數 n (1 ≦ n ≦ 100,當 n = 0 時所有輸入結束),代表一個圖的節點數。

接著有若干列(由單獨的一列「0」作結),每列開頭有一正整數 i (1 ≦ i ≦ n),代表接著的節點所共同有的起始節點。接著有若干個正整數 j (1 ≦ j ≦ n, j = 0 時代表該列輸入之結尾),代表有一個單向的邊從節點 i 通往節點 j 。

在單獨的一列「0」之後,還有一列輸入。該列開頭給定一整數,代表詢問的筆數。接著有詢問筆數個正整數(介於 1 ~ n 之間),代表起始節點。試問有多少個節點無法從起始節點直接地,或是經由其他節點間接地抵達?那些節點的編號是?輸出格式參見範例輸出。

注:起始節點不算作「被抵達」的節點,除非存在一路徑從起始節點走回到起始節點。參見範例輸入的測資。



範例輸入:
3
1 2 0
2 2 0
3 1 2 0
0
2 1 2
0


範例輸出:
2 1 3
2 1 3


解題思維:
就是單純地建出一張圖(利用連結串列(Linked List),或是鄰接矩陣(Adjacency Matrix)都可以),然後對於每個起始節點採取深度優先搜尋(Depth First Search,DFS)或是廣度優先搜尋(Breadth First Search,BFS),兩者皆可,去遍歷其能到達的節點。

在遍歷的過程中統計到達的節點數以及哪些可以從起始節點到達(除了起始節點,不能一開始就將其標為「抵達」,除非有另一個路徑到達起始節點)。然後在輸出的時候,無法抵達的節點數即是總節點數 - 可抵達之節點數,不能抵達的節點即是可以到達的節點以外的節點。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作