[USACO3.3] 骑马修栅栏 Riding the Fences

DFS 会一直钻到底，直到无路可走才把点放入栈中。
这意味着：最后访问的点最先入栈，最先访问的点最后入栈。(利用栈倒序的功能)
所以，我们在 DFS 内部按 $1 \to 500$ 的顺序从小到大遍历邻居，这样“小”的邻居会被先递归访问。
最终把栈里的元素弹出来（或者倒序输出数组），就是正确的、字典序最小的顺序。

代码

cpp

/**
 * Author by Rainboy blog: https://blog.roj.ac.cn github : https://github.com/rainboylvx
 * date: 2025-12-19 09:45:16
 */
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,m;
int a[maxn];
int g[505][505];
int deg[505];
std::vector<int> path;

void init(){
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        int u,v;
        std::cin >> u >> v;
        g[u][v]++;
        g[v][u]++;
        deg[u]++;
        deg[v]++;
    }
}

void dfs(int u) {
    // std::cout << u << "\n";
    for(int v = 1;v <= 500 ;++v ) // i: 1->500
    {
        if( g[u][v] > 0) {

            //删除边
            g[u][v] --;
            g[v][u] --;
            dfs(v);
        }
    }
    //回溯的时候加入点
    path.push_back(u);
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    init();

    int start_node = -1;
    for(int i = 1;i <= 500 ;++i ) // i: 1->505
    {
        if( deg[i] == 0) continue;

        //记录第一个可行的点
        if(start_node == -1 ) start_node = i;


        if( deg[i] % 2 == 1) 
        {
            start_node = i;
            break;
        }
    }
    dfs(start_node);
    for(int i = path.size()-1;i >=0 ;i--)
    {
        cout << path[i] <<"\n";
    }
    
    return 0;
}

[USACO3.3] 骑马修栅栏 Riding the Fences

目录

代码