首先非常痛心疾首地说一句，欧拉回路自己之前只是看过代码，知道思想，从来没有亲手实现过，所以，，，伤亡惨重！！！
欧拉回路是一个非常有意思的图论模型，因为伟大的数学家欧拉(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 }
需要注意的是，我们此处标记的是边（或者删除边）。因为欧拉道路或欧拉回路是可以一口气走到结束的，所以上面的代码可以放心写个循环，且递归后不必跳出，因为当返回该点时，该点所连的其他边必然已经被走过了。因此答案里存的就是一条完整的路径。
无序字母对：https://www.luogu.org/problemnew/show/P1341
这道题的话，还是浪费了很多时间，一是因为欧拉回路以前没写过，而是因为这道题答案保存那里有点玄学问题，默默改成栈就过了。字符的处理也需要注意一下。
1 #include<cstdio> 2 #include<stack> 3 using namespace std; 4 const int maxn=55; 5 int n,G[maxn][maxn],d[maxn]; 6 stack<int> ans; //用栈倒序保存答案 7 int toInt(char c) { //字符转为整数 8 if(c>=‘A‘&&c<=‘Z‘) return c-‘A‘+1; 9 return c-‘a‘+27; 10 } 11 char toChar(int i) { //整数转为字符 12 if(i>=1&&i<=26) return i-1+‘A‘; 13 return i-27+‘a‘; 14 } 15 void euler(int u) { 16 for(int v=1;v<=52;++v) 17 if(G[u][v]) { 18 G[u][v]=G[v][u]=0; //删边 19 euler(v); 20 } 21 ans.push(u); 22 } 23 int main() { 24 scanf("%d",&n); 25 char cu,cv; 26 int u,v; 27 for(int i=1;i<=n;++i) { 28 while((cu=getchar())==‘\n‘||cu==‘ ‘||cu==‘\r‘); //过滤无用字符 29 cv=getchar(); 30 u=toInt(cu),v=toInt(cv); 31 G[u][v]=G[v][u]=1; 32 ++d[u],++d[v]; //统计度数 33 } 34 int s=0,cnt=0; 35 for(int i=1;i<=52;++i) //找起点和判断是否存在欧拉道路 36 if(d[i]&1) { 37 ++cnt; 38 if(!s) s=i; 39 } 40 if(!cnt) for(int i=1;i<=52;++i) 41 if(d[i]) { 42 s=i; 43 break; 44 } 45 if(cnt&&cnt!=2) { 46 printf("No Solution\n"); 47 return 0; 48 } 49 euler(s); 50 if((int)ans.size()<n+1) printf("No Solution"); 51 while(!ans.empty()) { 52 int p=ans.top(); 53 ans.pop(); 54 printf("%c",toChar(p)); 55 } 56 putchar(‘\n‘); 57 return 0; 58 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9532164.html
