d536: 98台北縣 第三題：圖形迴圈偵錯問題

zerojudge連結

內容 ：

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

提示 ：

出處 ：

98北三區資訊學科能力競賽 (管理：pcshic)

解題策略

利用DFS走訪，遞迴函式DFS紀錄起始點與深度，超過最小深度不用繼續拜訪，DFS拜訪結束需還原成未拜訪過，下一個點為起點時計算，才會能拜訪每一個點。