题解：骑马修栅栏问题

一、题目背景

农民John每年要修理很多栅栏，他骑马经过每个栅栏进行修复，且不想重复经过同一个栅栏。需要找到一条路径，使每个栅栏恰好被经过一次，John可以从任意顶点开始和结束，最后按要求输出路径。

二、解题思路

本题是求图的欧拉路径问题。首先构建图的邻接矩阵来表示栅栏与顶点的连接关系，并记录每个顶点的度数。然后找到合适的起点（度数为奇数的顶点优先，若没有则从第一个有边相连的顶点开始）。接着使用深度优先搜索（DFS）遍历图，在遍历过程中删除已走过的边，最后逆序输出遍历得到的路径，这样就能保证输出的路径在要求的规则下是最小的。

具体步骤如下：
1. 定义相关数组和变量，包括表示图的邻接矩阵 g[N][N]，记录路径的数组 ans[1100]，记录每个顶点度数的数组 d[N]，顶点数 n（固定为500）和栅栏数 m。
2. 编写深度优先搜索函数 dfs：
- 遍历当前顶点 u 与其他顶点 i 的连接情况。
- 若存在连接（g[u][i]），则减少这条边的数量（因为无向图，所以 g[u][i] 和 g[i][u] 都减1），并递归调用 dfs(i) 继续搜索。
- 当从某个顶点出发的所有边都被访问完后，将该顶点加入路径数组 ans 中。
3. 在 main 函数中：
- 读取栅栏的数目 m，然后依次读取每条栅栏连接的两个顶点 a 和 b，更新邻接矩阵 g 和顶点度数数组 d。
- 找到合适的起点：先从顶点1开始找，若该顶点度数为0，则继续找下一个顶点；若存在度数为奇数的顶点，则将其作为起点。
- 从找到的起点开始进行深度优先搜索。
- 逆序输出路径数组 ans 中的顶点，即为所求的骑马路径。

三、代码逐段分析

（一）头文件和全局变量

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;

int n = 500, m;
int g[N][N];
int ans[1100], cnt;
int d[N];

1. 头文件：包含字符串操作（cstring）、输入输出（iostream）和算法（algorithm）相关的头文件，并使用标准命名空间。
2. 常量定义：const int N = 510; 定义顶点数量的上限。
3. 变量定义：
   • int n = 500, m;：n 固定为500表示顶点数，m 表示栅栏的数目。
   • int g[N][N];：二维数组，作为邻接矩阵存储图的边信息，g[i][j] 表示顶点 i 和顶点 j 之间边的数量。
   • int ans[1100], cnt;：ans 数组用于存储路径上的顶点，cnt 记录路径中顶点的数量。
   • int d[N];：数组记录每个顶点的度数。

（二）深度优先搜索函数 dfs

void dfs(int u)
{
    for (int i = 1; i <= n; i ++ )
        if (g[u][i])
        {
            g[u][i] --, g[i][u] -- ;
            dfs(i);
        }
    ans[ ++ cnt] = u;
}

1. 以顶点 u 为起点进行深度优先搜索：
   • 遍历所有可能的顶点 i（从1到 n），若顶点 u 和顶点 i 之间有边（g[u][i] 不为0）。
   • 减少这条边的数量（因为是无向图，所以 g[u][i] 和 g[i][u] 都减1），表示这条边已被走过，然后递归调用 dfs(i) 继续从顶点 i 进行搜索。
   • 当从顶点 u 出发的所有边都被访问完后，将顶点 u 加入路径数组 ans 中，cnt 自增1记录路径中的顶点。

（三）main 函数

int main()
{
    cin >> m;
    while (m -- )
    {
        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 <= n; i ++ )
        if (d[i] % 2)
        {
            start = i;
            break;
        }

    dfs(start);

    for (int i = cnt; i; i -- ) printf("%d\n", ans[i]);

    return 0;
}

1. 读取栅栏的数目 m，然后通过循环依次读取每条栅栏连接的两个顶点 a 和 b：
   • 更新邻接矩阵 g，g[a][b] 和 g[b][a] 都加1，表示顶点 a 和顶点 b 之间有一条边。
   • 更新顶点度数数组 d，d[a] 和 d[b] 都加1，表示顶点 a 和顶点 b 的度数各增加1。
2. 寻找合适的起点：
   • 先初始化起点 start 为1，然后通过循环判断 d[start] 是否为0，若为0则继续寻找下一个顶点，直到找到一个度数不为0的顶点。
   • 再通过循环遍历所有顶点，若存在度数为奇数的顶点，则将其作为起点 start，并跳出循环。
3. 从找到的起点 start 开始调用 dfs 函数进行深度优先搜索。
4. 最后逆序遍历路径数组 ans，输出路径上的每个顶点，每个顶点占一行。

四、时间复杂度和空间复杂度分析

（一）时间复杂度

1. 建图：读取栅栏信息并更新邻接矩阵和顶点度数，时间复杂度为 (O(m))，其中 m 是栅栏的数目。
2. 寻找起点：遍历顶点寻找合适的起点，最坏情况下时间复杂度为 (O(n))，其中 n 是顶点数（固定为500）。
3. 深度优先搜索：每个边最多被访问一次，时间复杂度为 (O(m))。
   总体时间复杂度为 (O(m + n))，在本题中 (n) 固定，主要取决于 (m) 。

（二）空间复杂度

1. 数组空间：邻接矩阵 g[N][N] 空间复杂度为 (O(n^2))，路径数组 ans[1100] 空间复杂度为 (O(m))（因为路径长度最大为 (m + 1)），顶点度数数组 d[N] 空间复杂度为 (O(n))。
   总体空间复杂度为 (O(n^2)) 。

希望这份题解能帮助你理解这道题的解题思路和代码实现。如果有任何疑问，欢迎随时提问。