[FGISC。Nanro] 未來開端

上回已談過DFS的基礎概念了，接下來我們來講講其中的幾個應用。

＊尤拉路徑(Euler Path)(一筆劃問題)
    有個很有名的圖論問題叫做「柯尼斯堡七橋問題」(參見http://0rz.tw/bb35H)
    當年尤拉解決了這個問題，並証明了這種方法並不存在
    也找出了可解決的「一筆劃問題」的條件
    如果上面的東西讓你搞不清楚
    那麼回想一下小時候，書上會有些圖叫你嘗試是否能用一筆劃將之畫完嗎？
    那就是尤拉路徑。
    尤拉路徑可分為尤拉迴路(Euler Cycle)和尤拉鏈(Euler Chain)
    其差異就是「奇點」的數量。
    尤拉路徑的定理是在圖形中，必須要有「零個」或是「兩個」奇點
    而所謂的奇點就是「與它連接的路徑只有奇數個」
    Cycle就是奇點0個的情況，Chain則是奇點2個的情況。

    好，知道了其定義，接下來我們來看一下ACM裡的DFS Euler Path Problem-Q291
    http://luckycat.kshs.kh.edu.tw/homework/q291.htm

    使用DFS來實作，因為這個圖形已經固定了樣貌，所以我們可以直接開始。

    她的規定是要從1為起點，由觀察可知2為其終點。
    不過真正的「完成」條件是：把所有的路徑走過一次。
    也就是如上次提及的方式，可用二維陣列紀錄此路可否通與是否有走過這段路
    然後再進入遞迴之中尋求路徑
    以第一組測資123153452來說：
    我從第一個點1開始，發現我可以走到2.3.5三個點
    所以我就先走到2，發現又可以走到3.5(通往1那條已經走過了)
    然後就走到3，發現可以走到1.4.5(通往2那條走過了)
    於是我往1走去，發現又可以走到5(其他條皆走過了)
    在5的時候，又可以走到2.3.4
    所以我又走到了2，卻發現往1.3的兩條路都走過了
    這時候遞迴就會回到上一層，從5改走到了3
    接下來又可以走4，從4又只能走到5，然後走到了2→完成

    好啦，大概就是這樣了～本題算是DFS很基礎的題目
    下一次會談排列組合的應用就會比較複雜:)
    如果有興趣可以先看看441.10098這些題目～