首先非常痛心疾首地說一句，歐拉回路自己之前只是看過代碼，知道思想，從來沒有親手實現過，所以，，，傷亡慘重！！！

歐拉回路是一個非常有意思的圖論模型，因為偉大的數學家歐拉(euler)而得名。傳說，曾經人們沉迷于一個七橋問題，想找出一種走法不重復地經過七座橋（具體請自行了解）。歐拉指出了不存在這樣的走法，并由此歸結出了“一筆畫問題”。用圖論的語言來說，就是找一條路徑不重復地走過所有的邊。

實際上，從一個點出發，不重復地經過所有的邊，這叫做歐拉道路；如果這條路徑起點和終點相同，才稱為歐拉回路。另外，如果一個圖存在歐拉道路，那么稱為半歐拉圖，如果一個圖存在歐拉回路，稱為歐拉圖。

對于無向圖，存在歐拉道路的條件是只有兩個或不存在奇點（度為奇數的點），存在歐拉回路的條件是不存在奇點。對于有向圖，存在歐拉道路的條件是只有兩個點的入度和出度不相同，并且其中一個點（起點）的出度比入度大1，另一個點（終點）的入度比出度大1，或者所有點的入度和出度都相等，存在歐拉回路的條件是所有點的入度和出度都相等。當然圖必須是連通的。

尋找歐拉道路或者歐拉回路是比較簡單的，可以使用DFS。起點的確定也需要注意，如果找歐拉道路，必須找到相應的起點，而歐拉回路任選一個點作為起點即可。

1 void euler(int u) { 2 for(int v=1;v<=n;++v) 3 if(G[u][v]) { 4 G[u][v]=G[v][u]=0; //有向圖則改為G[u][v]=0; 5 euler(v); 6 } 7 ans.push(u); 8 } 尋找歐拉道路或歐拉回路（無向圖）

需要注意的是，我們此處標記的是邊（或者刪除邊）。因為歐拉道路或歐拉回路是可以一口氣走到結束的，所以上面的代碼可以放心寫個循環，且遞歸后不必跳出，因為當返回該點時，該點所連的其他邊必然已經被走過了。因此答案里存的就是一條完整的路徑。還有需要注意要先進行DFS遍歷，最后存儲答案，這叫做套圈法，可以處理環相連的情況。

?

無序字母對：https://www.luogu.org/problemnew/show/P1341

---

?

這道題的話，還是浪費了很多時間，一是因為歐拉回路以前沒寫過，而是因為這道題答案保存那里有點玄學問題，默默改成棧就過了（其實是因為無語的數組溢出，導致了奇怪的輸出）。字符的處理也需要注意一下。如果直接讀入到字符數組會WA的很慘。別問我是怎么知道的。。。

1 #include <cstdio> 2 #include <stack> 3 4 using namespace std; 5 6 const int maxa = 55; 7 8 inline int toInt(char c) { 9 if (c <= 'Z') return c - 'A' + 1; 10 else return c - 'a' + 27; 11 } 12 13 inline char toChar(int i) { 14 if (i <= 26) return i - 1 + 'A'; 15 else return i - 27 + 'a'; 16 } 17 18 int G[maxa][maxa], degree[maxa]; 19 20 stack<int> ans; 21 22 void euler(int u) { 23 for (int v = 1; v <= 52; ++v) 24 if (G[u][v]) { 25 G[u][v] = G[v][u] = 0; 26 euler(v); 27 } 28 ans.push(u); 29 } 30 31 int main() { 32 int n, a, b, s1 = 0, s2 = 0, cnt = 0; 33 scanf("%d", &n); 34 for (int i = 1; i <= n; ++i) { 35 char u = getchar(); 36 while (u == '\n' || u == ' ' || u == '\r') 37 u = getchar(); 38 char v = getchar(); 39 a = toInt(u), b = toInt(v); 40 G[a][b] = G[b][a] = 1; 41 ++degree[a], ++degree[b]; 42 } 43 for (int i = 1; i <= 52; ++i) { 44 if (degree[i] && !s1) s1 = i; 45 if (degree[i] % 2) { 46 ++cnt; 47 if (!s2) s2 = i; 48 } 49 } 50 if (cnt && cnt != 2) printf("No Solution"); 51 else { 52 if (cnt) euler(s2); 53 else euler(s1); 54 if ((int)ans.size() != n + 1) printf("No Solution"); 55 else while (!ans.empty()) { 56 printf("%c", toChar(ans.top())); 57 ans.pop(); 58 } 59 } 60 return 0; 61 } AC代碼

?

轉載于:https://www.cnblogs.com/Mr94Kevin/p/9532164.html

總結

以上是生活随笔為你收集整理的欧拉回路【洛谷习题】无序字母对的全部內容，希望文章能夠幫你解決所遇到的問題。

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