相信大多數(shù)人都聽說過著名的七橋問題——沒聽過？那換個通俗的名字：一筆畫問題

我們給出一個圖（先不考慮有向無向）：

若從一個點開始遍歷這個圖，每條邊都恰好經(jīng)過一次，那么我們把這條路徑稱為歐拉路徑（該圖能夠一筆畫出）；

若這條路徑的起點與終點相同，那么我們稱這條路徑為歐拉回路。

顯而易見，若一條路徑是歐拉回路，那么它也一定是歐拉路徑。

定義之后，就是該如何判斷一個圖是否存在歐拉路徑了~

首先，我們要看給出的圖在看做無向圖后是否聯(lián)通（即各個點之間是否可以兩兩到達(dá)）

若該圖在看做無向圖后不聯(lián)通，那么顯然不存在歐拉路徑

然后定義：

• 對于無向圖的一個節(jié)點，其度數(shù)等于于其相連的邊的數(shù)量，可根據(jù)其度數(shù)分為奇節(jié)點（度數(shù)為奇數(shù)的點）與偶節(jié)點（度數(shù)為偶數(shù)的點）

• 對于有向圖的一個節(jié)點，其出度等于以它為起點的邊的數(shù)量，其入度等于以它為終點的邊的數(shù)量

再根據(jù)圖是否無向進(jìn)行探討：

1. 該圖為無向圖：

   首先，若圖中沒有奇節(jié)點（全部為偶節(jié)點），那么每個節(jié)點都存在2k條路徑，該點可以通過k條路徑向外走，再通過k條路徑走回來，顯然，這是一個歐拉回路。

   并且我們可以看出來，在歐拉回路中，任何一個點都可以作為起點并在遍歷一遍后回到該點。

   其次，若圖中有兩個奇節(jié)點s,t，我們將這兩個奇節(jié)點相連后，會發(fā)現(xiàn)這兩個節(jié)點也變成了偶節(jié)點，此時與沒有奇節(jié)點的情況相同，存在一條歐拉回路，以s為起點最后到達(dá)t回到s；然后我們再將剛才增加的那條邊刪去，s與t就不相連了，此時以s為起點，在來到t時無法回到s，于是t就成了這條歐拉路徑的終點（s和t可以交換位置）。

   總結(jié)一下：

   無向圖歐拉路徑：圖中恰好存在兩個奇節(jié)點，這兩個度數(shù)為奇數(shù)的點即為歐拉路徑的?起點?s?和?終點?t 。

   無向圖歐拉回路：圖中沒有奇節(jié)點（所有點的度數(shù)都是偶數(shù)），起點 s?和終點?t?可以為任意點。

2. 該圖為有向圖：

   若所有的點出度與入度相同（都為k），則一個點可以通過k條邊向外走再通過k條邊回到該點，明顯構(gòu)成一條歐拉回路。

   當(dāng)圖中恰好存在一個點s出度比入度多一，且恰好存在一個點t入度比出度多一時，我們構(gòu)建一條t到s的有向邊，此時情況變成了所有點的出度與入度相同，存在一條歐拉回路從s開始最后到達(dá)t回到s；當(dāng)t到s的這條有向邊被去掉后，在最后到達(dá)t后無法從t回到s，此時s就成為了這條歐拉路徑（因為無法回到起點s）的起點，t為這條歐拉路徑的終點（s和t是固定的）。

   總結(jié)一下：

   有向圖歐拉路徑：圖中恰好存在?1?個點出度比入度多?1（這個點即為?起點?s），11?個點入度比出度多?1（這個點即為?終點?t），其余節(jié)點出度=入度。
   

   有向圖歐拉回路：所有點的入度等于出度（起點 s?和終點 t?可以為任意點）。

   在討論過歐拉回路以及歐拉路徑的存在性后，接下來就該考慮代碼實現(xiàn)了：

例題：洛谷P7771 【模板】歐拉路徑

首先讀題，給出的圖是有向圖，并且要求按照字典序輸出，所以我們再輸入后要對一個節(jié)點所指向的邊進(jìn)行排序；因為我們是用的dfs進(jìn)行的遍歷，所以相對應(yīng)的節(jié)點需要存在一個棧里面，最后倒序輸出就是遍歷的順序。

我們首先判斷這個圖是否有歐拉路徑或歐拉回路：

在判斷歐拉回路（或歐拉路徑）存在后，我們就需要遍歷這個圖且使其字典序最小了：

最后輸出棧內(nèi)的節(jié)點就是路徑順序了：

還有一個要注意的點，就是如果存在歐拉路徑的話，s節(jié)點是不會初始化的，因此要將s的初始值賦值為1（保證字典序最?。?/p>

AC Code：

完結(jié)撒西秀園~

祈愿流浪者和心海