d536. 3. 圖形迴圈偵錯問題 - 高中生程式解題系統

內容

一個有向圖(directed garph)是由數個節點(node)和節點與節點之間的連結(link)所組成。圖形中的迴圈是指以某個節點為基準，沿著連結前進，最後會回到原來的節點，則所經過的路徑就組成迴圈。形成迴圈時的連結不可以被重複走兩次。

以圖一為例，有五個節點(編號 A,E,D,B,M)和7個連結(AE,ED,DE,DA,DB,BA,MB)，其中有三種大小不同的迴圈存在，例如：A→E→D→B→A(此迴圈的連結個數為4),D→A→E→D(此迴圈的連結個數為3),E→D→E(此迴圈的連結個數為2)。你的任務就是要寫一個程式來偵測一個圖形是不是有迴圈，並且列出最短迴圈的連結個數。以圖一為例，最短迴圈的連結個數為2。

在圖二，有一個節點(編號 V)和1個連結(VV)，最短迴圈的連結個數為1。

輸入說明

第一行有一個正整數m(1<=m<=10)，m代表圖形中有幾個連結(link)。
第二行到第m+1行是圖形的m個連結。每個連結由兩個大寫英文字母(A到Z)代表，如FD指的是一個F節點到D節點。所有的連結都是單向連結。

輸出說明

輸出圖形上的m個連結最短迴圈的節點數，沒有迴圈就輸出"0"。

範例輸入 #1

輸入範例一：
3
AE
EA
BA
輸入範例二：
4
AB
BC
CD
AD

範例輸出 #1

輸出範例一：
2
輸出範例二：
0

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <1K
公開測資點#3 (20%): 1.0s , <1K
公開測資點#4 (20%): 1.0s , <1K

提示：

標籤:

出處:

98學年度北基區資訊學科能力競賽 [管理者：

Unknown User

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」