骑马修栅栏

欧拉路径 DFS T3 1124. 骑马修栅栏 - AcWing题库 农民John每年有很多栅栏要修理。

他总是骑着马穿过每一个栅栏并修复它破损的地方。

John是一个与其他农民一样懒的人。

他讨厌骑马，因此从来不两次经过一个栅栏。

你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。

John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。

每一个栅栏连接两个顶点，顶点用 $1$ 到 $500$ 标号(虽然有的农场并没有 $500$ 个顶点)。

一个顶点上可连接任意多( $\ge 1$ )个栅栏。

所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。

你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。

我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个 (也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的，等等)。

输入数据保证至少有一个解。

输入格式

第 $1$ 行:一个整数 $F$，表示栅栏的数目;

第 $2$ 到 $F+1$ 行:每行两个整数 $i,j$ 表示这条栅栏连接 $i$ 与 $j$ 号顶点。

输出格式

输出应当有 $F+1$ 行，每行一个整数，依次表示路径经过的顶点号。

注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。

数据范围

$1\le F\le 1024$,
$1\le i,j\le 500$

输入样例：

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

思路

给一个无向图, 可以从任意一个非孤立点出发, 走到任何一个点上, 且经过所有的边。也就是欧拉路径问题。

先求出是否无解： 1）无向图, 只有当度数为奇数的点有0个或者2个时有解 2）有向图, 要么所有点的出度均等于入度;要么除了两个点之外，其余所有点的出度等于入度，剩余的两个点:一个满足出度比入度多1(起点)，另一个满足入度比出度多1(终点).

但这里还要求是 500进制 最小的数, 也就是按字典序搜索。 根据欧拉回路搜索过程, 从一个点出发也一定会再回来, 且答案是逆序存储, 故假如从 $i$ 点出发, 下一个点是 $j$, 那么对应到答案就是 $ij\dots ji$ , 显然, 我们需要选择能走的最小的 $j$。 若边数太多需要用邻接表时, 得排个序, 而这里点数比较小, 可以直接从小到大枚举。

代码流程：

1. 读入边并统计出入度
2. 找到起点start, 先定义为度数为0的点（0个时）
3. 然后遍历所有点判断是否存在度数为奇数的点, 若有则为起点（2个时）
4. 从起点进行DFS搜索
5. 输出答案

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 550, M = 1026;
int g[N][N];
int d[N];
int n;
int res[M];
int cnt;
 
void dfs(int u)
{
    for(int i = 1; i <= 500; i++)
    {
        if(g[u][i])
        {
            g[u][i]--, g[i][u]--;
            dfs(i);
        }
    }
    res[++cnt] = u;
}
 
int main()
{
    cin >> n;
    for(int i = 0; i < n;i ++)
    {
        int a,b;
        cin >> a >> b;
        g[a][b]++, g[b][a]++;
        d[a]++, d[b]++;
    }
    
    int start = 1;
    while(!d[start]) start++;
    for(int i = 1; i <= 500; i++)
        if(d[i] & 1)
        {
            start = i;
            break;
        }
    dfs(start);
    
    for(int i = cnt; i; i--) cout << res[i] << "\n";
    
    
    
    return 0;
}