d536: 3. 圖形迴圈偵錯問題
標籤 :
通過比率 : 95% (138 人 / 146 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-09-26 17:50

內容

一個有向圖(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"。

範例輸入
輸入範例一:
3
AE
EA
BA
輸入範例二:
4
AB
BC
CD
AD
範例輸出
輸出範例一:
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學年度北基區資訊學科能力競賽 [編輯:
pcshic (PCSHIC)
]


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