柯尼斯堡七桥问题
18世纪时，欧洲的一个小城柯尼斯堡有七座桥，连接了四个地方，如下图所示。人们聊天时，有人提出这样一个问题：是否存在一种方法，能够从一个地点出发，经过每座桥一次且仅一次，最后回到起点。人们讨论了很长时间，都没有找到方案。
欧拉出手
这个问题引起了欧拉的兴趣。他稍微研究了以下，很快就证明了该问题是无解的。即不存在一种走法，能够从某个地点出发，经过每座桥一次且仅一次，最后回到起点。
欧拉是如何思考这个问题的呢？
首先，他简化了一下。将四块陆地看做四个点，将七座桥看做是七条边，得到如下的图：
现在只需要在A、B、C、D四点中选一个点为起点，一笔画完该图，最后回到起点。
我们发现，如果存在这样一条线路，那么与每个点相连接的边一定是偶数条。
这很显然，因为对于起点而言，一定是先出后进，而对于其他点，一定是先进后出。每条边只能走一次。这就要求与该点相连的边必须是偶数条。
而上图不符合这个条件，所以他是无解的。
我们用度来表示一个点相连的边数。如果一个点的度为偶数，则称为偶点；否则称为奇点。
欧拉不仅解决了七桥问题，还得出了一个结论，开创了人类对图论的研究。
- 如果所有的点都是偶点，则该图可以一笔画完，并回到起点。
- 如果仅存在两个奇点，则可以从一个奇点出发，一笔画完，最终到达另一个奇点。
- 其他情况，图不能一笔画完
人们把能够一笔画完并回到起点的图，称为欧拉回路；把能够一笔画完，但不能回到起点的图，称为欧拉通路。
一笔画问题
我们已经知道如何判断一个图是不是欧拉回路或者欧拉通路。
如果是欧拉回路或者欧拉通路，如何输出一种一笔画完的方案呢？
这样的方案可能有多种，我们只需要输出任意一种即可。
可以使用dfs，走过的边马上删掉, 如果一个点的边都删完了，则将该点加入到一个序列。dfs结束后，该序列即为一笔画的路径。
void dfs(int s){
vis[s] = 1;
for(int i = 1; i <= n; i++){
if(arr[s][i]){
arr[s][i] = arr[i][s] = 0;
dfs(i);
}
}
path[top++] = s;
}
这是一个简单而神奇的算法。它有点类似于树的后序序列。
但改为先序序列就不对了。这很好理解。因为来到分叉口，如果选择一条错误的路，那么有些分支就永远错过了。后面虽然递归返回时能够我们重新光顾这个岔路口，但是在路径上不是连续的。
而改成后序序列后，在任何一个分岔路口，不管选择那一条走，后序序列都能够保证最后回到这个岔路口。等到所有的岔路口都走了并返回后，再来时的路返回，这样路径就接上了。
比如有一条边\((i,j)\),现在从\(i\)走到了\(j\)，那么返回时能够保证\(j\)的所有其他岔路都走了并且返回了以后，再返回到\(i\)点。
例题1：
对给定的一个无向图，判断能否一笔画出。若能，输出一笔画的先后顺序，否则输出“No Solution!”
所谓一笔画出，即每条边仅走一次，每个顶点可以多次经过。
输出字典序最小的一笔画顺序。
分析：首先判断是不是一笔画的图？如果有0个奇点或者2个奇点，则可以一笔画，否则直接输出"No Solution!".
如何保证字典序最小呢？
因为我们是后序遍历，先访问的点，实际上是后进入队列的。所以， 我们按照编号由小到大的顺序依次dfs，最后将队列逆序输出即可。
如果全为偶点，我们以\(1\)号点为起点；如果有两个奇点，则从编号较小的奇点做dfs。
#include <bits/stdc++.h>
using namespace std;
#define maxn 105
int arr[maxn][maxn];
int n, m, top, du[maxn];
int odds, start;
bool noans;
int path[maxn * maxn];
bool vis[maxn];
int ecnt;
int visit;
void dfs(int s){
vis[s] = 1;
for(int i = 1; i <= n; i++){
if(arr[s][i]){
arr[s][i] = arr[i][s] = 0;
dfs(i);
}
}
path[top++] = s;
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
scanf("%d", &arr[i][j]);
if(arr[i][j] == 1) du[i]++, ecnt++;
}
}
ecnt /= 2;
for(int i = n; i > 0; i--){
if(du[i] % 2 == 1) {
odds++;
start = i;
}
}
if(odds == 0){
dfs(1);
}
else if(odds == 2){
dfs(start);
}
else noans = 1;
if(noans == 1 || top != ecnt + 1)printf("No Solution!\n");
else {
for(int i = top - 1; i >= 0; i--){
printf("%d ", path[i]);
}
}
return 0;
}
例题二
题目描述：
给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。
如果有多种方案，请输出前面的字母的ASCII编码尽可能小的（字典序最小）的方案
分析
将52个字母看做52个点，如果出现一个字母对，则将对应的两个点连一条无向边。
判断是否是欧拉回路，输出一笔画的顺序即可。