題目鏈接：http://poj.org/problem?id=1041

思路：懶得寫了，直接copy吧：對于一個圖可以從一個頂點(diǎn)沿著邊走下去，每個邊只走一次，所有的邊都經(jīng)過后回到原點(diǎn)的路。一個無向圖存在歐拉回路的充要條件是每個頂點(diǎn)的度是偶數(shù)， 對于有向圖存在歐拉回路的條件是每個頂點(diǎn)的出度等于入度（就是出去的邊數(shù)等于進(jìn)來的邊數(shù)）。根據(jù)這個首先判斷存在歐拉回路不， 如果存在然后用DFS去找歐拉回路。DFS的思想等效于先找一個環(huán)，然后對環(huán)上所有點(diǎn)遞歸DFS，并且把這些遞歸產(chǎn)生的路插入這個環(huán)中。 實(shí)際上程序?qū)崿F(xiàn)起來很簡單，遞歸完成后不需要單獨(dú)做插入。

由于圖已經(jīng)保證連通，首先用度數(shù)是否是偶數(shù)，判斷圖是否是歐拉圖，然后，輸出最小升序，其實(shí)就是每次都從小往大的搜，先搜得一個最小序環(huán)，然后對環(huán)上的每一點(diǎn)進(jìn)行搜索，其實(shí)對于歐拉圖而言，每個點(diǎn)要么就只剩一個點(diǎn)，什么也搜不到了，要么還有一個環(huán)，只要把環(huán)上路徑全都插入到對應(yīng)位置上，用棧存路徑，每次只有回溯到當(dāng)前點(diǎn)，就是說當(dāng)前點(diǎn)的后繼都已經(jīng)搜過了的時候，才把當(dāng)前點(diǎn)入棧，這樣一來倒著輸出，就能得到一個歐拉回路，而且是最小升序。

http://paste.ubuntu.com/5992690/

?

轉(zhuǎn)載于:https://www.cnblogs.com/wally/p/3263538.html

總結(jié)

以上是生活随笔為你收集整理的poj 1041(欧拉回路+输出字典序最小路径)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。