【题目描述】
农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。
John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。
每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(≥1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。
你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个 (也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的，等等)。 输入数据保证至少有一个解。
【输入】
第1行:一个整数F(1≤F≤1024)，表示栅栏的数目;
第2到F+1行:每行两个整数i,j(1≤=i,j≤500)表示这条栅栏连接i与j号顶点。
【输出】
输出应当有F+1行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。
【输入样例】
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6
【输出样例】
1
2
3
4
2
5
4
6
5
7
分析
- 此题就是一个 1341：【例题】一笔画问题——欧拉(回)路 的经典例题，只不过和一笔画又有点不一样；这个题你不知道有几个顶点，你不知道顶点从几到几开始，而且要求路径输出的次序，以及此题两个点之间存在多条边；
- 思路：和一笔画一样，找编号最小的奇点，然后从奇点开始搜索，然后把路径存在path；
- 细节：此题的栅栏就是两个顶点的一条边，然后两个顶点间会存在多条边，然后我们要用++（看代码）；然后要找顶点的编号范围，不然我们搜索都不知道从哪搜起，到哪结束（采用maxx，minn，分别保存存在的顶点的最大编号、最小编号）；此题找欧拉路或者欧拉回路，然后我们找奇度顶点，赋值给start（默认就是编号最小的顶点）；然后从奇点出发，开始搜索；
#include <bits/stdc++.h>
using namespace std;
const int N = 505, INF = 0x3f3f3f3f;
int a[N][N], path[2 * N];
int dis[N];//顶点的度
int F, x, y, maxx, minn = INF, cnt;//maxx:最大顶点的编号，minn：最小的顶点编号
void dfs(int u) {
//搜索范围：minn，maxx
for (int i = minn; i <= maxx; ++i) {
if (a[u][i]) {
a[u][i]--, a[i][u]--;
dfs(i);
}
}
path[++cnt] = u;
}
int main() {
cin.tie(0);
cin >> F;
for (int i = 0; i < F; ++i) {
cin >> x >> y;
//两点之间可能有多条边连接，所有要用++
//a[x][y] = a[y][x] = 1;
a[x][y]++, a[y][x]++;
dis[x]++, dis[y]++;
//确定顶点的范围，也是为了找最小点来开始搜索用
minn = min(minn, min(x, y));
maxx = max(maxx, max(x, y));
}
//欧拉回路或者欧拉路
int start = minn;//初始化最小的顶点
for (int i = minn; i <= maxx; ++i) {
if (dis[i] % 2) {
//找最小那个奇点
start = i;
break;
}
}
dfs(start);
for (int i = cnt; i >= 1; --i) {
cout << path[i] << endl;
}
return 0;
}