#1181 : 歐拉路·二

時間限制:10000ms 單點時限:1000ms 內存限制:256MB

描述
在上一回中小Hi和小Ho控制著主角收集了分散在各個木橋上的道具，這些道具其實是一塊一塊骨牌。

主角繼續往前走，面前出現了一座石橋，石橋的盡頭有一道火焰墻，似乎無法通過。

小Hi注意到在橋頭有一張小紙片，于是控制主角撿起了這張紙片，只見上面寫著：

將M塊骨牌首尾相連放置于石橋的凹糟中，即可關閉火焰墻。切記骨牌需要數字相同才能連接。
——By 無名的冒險者
小Hi和小Ho打開了主角的道具欄，發現主角恰好擁有M快骨牌。

小Ho：也就是說要把所有骨牌都放在凹槽中才能關閉火焰墻，數字相同是什么意思？

小Hi：你看，每一塊骨牌兩端各有一個數字，大概是只有當數字相同時才可以相連放置，比如：

小Ho：原來如此，那么我們先看看能不能把所有的骨牌連接起來吧。

提示：Fleury算法求歐拉路徑
小Ho：這種簡單的謎題就交給我吧！

小Hi：真的沒問題么？

<10分鐘過去>

小Ho：啊啊啊啊啊！搞不定啊！！！骨牌數量一多就亂了。

小Hi：哎，我就知道你會遇到問題。

小Ho：小Hi快來幫幫我！

小Hi：好了，好了。讓我們一起來解決這個問題。

<小Hi思考了一下>

小Hi：原來是這樣。。。小Ho你仔細觀察這個例子：

因為相連的兩個數字總是相同的，不妨我們只寫一次，那么這個例子可以寫成：3-2-4-3-5-1。6個數字剛好有5個間隙，每個間隙兩邊的數字由恰好對應了一塊骨牌。

如果我們將每一個數字看作一個點，每一塊骨牌看作一條邊。你覺得是怎么樣的呢？

小Ho：以這個例子來說的話，就是：

要把所有的骨牌連起來，也就是把所有的邊都走一次。咦，這不是歐拉路問題么！

小Hi：沒錯，這問題其實就是一個歐拉路的問題，不過和上一次不一樣的在于，這一次我們要找出一條歐拉路徑。

小Ho：那我們應該如何來找一條路徑呢？

小Hi：我們還是借用一下上次的例子吧

使用我們上一次證明歐拉路判定的方法，我們在這個例子中找到了2條路徑：

L1: 4-5-2-3-6-5 L2: 2-4-1-2

假設我們棧S，記錄我們每一次查找路徑時的結點順序。當我們找到L1時，棧S內的情況為：

S: 4 5 2 3 6 5 [Top]

此時我們一步一步出棧并將這些邊刪除。當我們到節點2時，我們發現節點2剛好是L1與L2的公共節點。并且L2滿足走過其他邊之后回到了節點2。如果我們在這個地方將L2先走一遍，再繼續走L1不就剛好走過了所有邊么。

而且在上一次的證明中我們知道，除了L1之外，其他的路徑L2、L3…一定都滿足起點與終點為同一個點。所以從任意一個公共節點出發一定有一條路徑回到這個節點。

由此我們得到了一個算法：

在原圖中找一個L1路徑

從L1的終點往回回溯，依次將每個點出棧。并檢查當前點是否還有其他沒有經過的邊。若存在則以當前點為起點，查找L2，并對L2的節點同樣用棧記錄重復該算法。

當L1中的點全部出棧后，算法結束。

在這里我們再來一個有3層的例子：

在這個例子中：

L1: 1-2-6-5-1 L2: 2-3-7-2 L3: 3-4-8-3

第一步時我們將L1壓入棧S，同時我們用一個數組Path來記錄我們出棧的順序：

S: [1 2 6 5 1] Path:

然后出棧到節點2時我們發現了2有其他路徑，于是我們把2的另一條路徑加入：

S: 1 [2 3 7 2] Path: 1 5 6

此時L2已經走完，然后再開始彈出元素，直到我們發現3有其他路徑，同樣壓入棧：

S: 1 2 [3 4 8 3] Path: 1 5 6 2 7

之后依次彈出剩下的元素：

S: Path: 1 5 6 2 7 3 8 4 3 2 1

此時的Path就正好是我們需要的歐拉路徑。

小Ho：原來這樣就能求出歐拉路，真是挺巧妙的。

小Hi：而且這個算法在實現時也有很巧妙的方法。因為DFS本身就是一個入棧出棧的過程，所以我們直接利用DFS的性質來實現棧，其偽代碼如下：

DFS(u):While (u存在未被刪除的邊e(u,v))刪除邊e(u,v)DFS(v)EndPathSize ← PathSize + 1Path[ PathSize ] ← u

小Ho：這代碼好簡單，我覺得我可以實現它！

小Hi：那么實現就交給你了

小Ho：沒問題！交給我吧

輸入
第1行：2個正整數，N,M。分別表示骨牌上出現的最大數字和骨牌數量。1≤N≤1,000，1≤M≤5,000

第2…M+1行：每行2個整數，u,v。第i+1行表示第i塊骨牌兩端的數字(u,v)，1≤u,v≤N

輸出
第1行：m+1個數字，表示骨牌首尾相連后的數字

比如骨牌連接的狀態為(1,5)(5,3)(3,2)(2,4)(4,3)，則輸出"1 5 3 2 4 3"

你可以輸出任意一組合法的解。

樣例輸入

5 5 3 5 3 2 4 2 3 4 5 1

樣例輸出

1 5 3 4 2 3

思路：

無向圖：
基本思想：
走過的邊刪除（得到新子圖），能不走橋就不走橋【刪除該邊圖（子圖）不連通】

算法偽代碼：
看上面題目~

如果是歐拉圖，從1開始搜索。
如果是半歐拉圖，隨便選一個奇度頂點開始搜索。

這題一大坑點是，兩點可能有重邊！！，所以標記邊訪問過，不能直接標記為0，而要--!!

AC代碼：

#include <iostream> #include <cstring> using namespace std; const int N = 1e3+5; int mp[N][N]; int d[N]; int n,m; void dfs(int s) {for(int i = 1; i <= n; i++){if(mp[s][i]){//這里要注意！！mp[s][i]--;mp[i][s]--;dfs(i);}}cout<<s<<" "; } int main() {cin>>n>>m;int x,y;while(m--){cin>>x>>y;mp[x][y]++;mp[y][x]++;d[x]++;d[y]++;}int cnt = 0;int s = 1;for(int i = 1; i <= n; i++){cnt += d[i]&1;if(d[i]&1) s = i;}if(cnt==0 || cnt==2){dfs(s);cout<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的#1181 : 欧拉路·二（无向图的欧拉路）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。