Embedded Files
尤拉迴路(Euler Circuit)
尤拉迴路(Euler Circuit)是給定一個圖形，判斷是否有可能經過圖形中每一個邊剛好一次，可以由起始點走回到起始點，若可以找出這樣的迴路稱作尤拉迴路(Euler Circuit)。
尤拉路徑(Euler Trail)是給定一個圖形，判斷是否有可能經過圖形中每一個邊剛好一次，可以由起點走到終點，而起點與終點不一定要相同，若可以找出這樣的路徑稱作尤拉路徑(Euler Trail)，很明顯尤拉迴路(Euler Circuit)也是尤拉路徑(Euler Trail)。
不難可以想到，對於起點與終點外的任何一個點，有進入該點的邊，就要有可以走出去的邊，才可以經由邊進出每個點，可以計算每個節點的進入邊的個數與走出去邊的個數，來判定是否有尤拉迴路(Euler Circuit)或尤拉路徑(Euler Trail)。
可以歸納出以下結論。
(一)尤拉路徑
給定最多20個節點以內的有向圖，每個節點編號由0開始編號，且節點編號皆不相同，相同起點與終點的有向邊可以重複，請判斷是否可以形成尤拉路徑。
輸入說明
輸入正整數m，表示圖形中有m個有向邊，接下來有m行，每個邊輸入兩個節點編號，保證節點編號由0到19。
輸出說明
請找出是否可以形成尤拉路徑。
範例輸入(一)
5
0 1
1 4
4 5
5 6
6 0
範例輸出(一)
可以找到尤拉路徑
範例輸入(二)
5
0 1
1 4
4 5
7 6
6 7
範例輸出(二)
無法找到尤拉路徑
(a)解題想法
使用陣列indeg與outdeg紀錄每個點進入的邊與出去的邊個數，變數nal紀錄圖形中點的個數，根據陣列indeg與outdeg統計所有點中進入的邊與出去的邊個數多1個的節點數到nin，所有點中出去的邊與進入的邊個數多1個的節點數到nout，所有點中進入的邊與出去的邊個數相同的節點數到nequ，經由nin、nout、nequ、nal判斷是否可能有尤拉路徑，最後使用深度優先搜尋判斷圖形是否可以連通，若可以連通則確定有尤拉路徑。
(b)程式碼
(c)程式結果預覽
按下「執行->編譯並執行」，結果顯示在螢幕如下。
(二)串接英文單字
給定最多1000個單字，將所有單字的首尾進行串接，例如：cat可以與tiger串接，tiger後面可以串接rain，請判斷是否將所有輸入的單字首尾可以串接起來，單字可能會有相同的首尾字母，不一定要串接回起始單字的字首。
輸入說明
輸入正整數m，表示有m個單字要輸入，接下來有m行，每行輸入一個單字，保證單字一定都是小寫字母組成。
輸出說明
請找出是否可以串接，若可以串接則顯示「可以串接」，否則輸出「無法串接」。
範例輸入(一)
5
john
null
len
no
open
範例輸出(一)
可以串接
範例輸入(二)
5
john
null
long
object
table
範例輸出(二)
無法串接
(a)解題想法
單字的首尾字母可以想成一個有向邊，從字首字母連到字尾字母，是否可以串接，且起始點與終點單字不一定要同一個單字，就是要找尋是否存在尤拉路徑，其餘與第14-2-1節解題想法相同。
(b)程式碼
(c)程式結果預覽
按下「執行->編譯並執行」，結果顯示在螢幕如下。
Page updated
Google Sites
Report abuse