Embedded Files
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拜訪結束需還原成未拜訪過，下一個點為起點時計算，才會能拜訪每一個點。
Page updated
Google Sites
Report abuse