#include <cstdio>
#include <vector>
#include <algorithm>
#define min(A, B) (A < B ? A : B)
#define INF 1e9

const int MX = 5010;

std::vector <int> G[MX];

namespace solveTree {
bool vis[MX];

void DFS(int u) {
    printf("%d ", u);
    vis[u] = true;
    std::sort(G[u].begin(), G[u].end());

    for (int v : G[u]) {
        if (not vis[v]) {
            DFS(v);
        }
    }
}
}

namespace solveCyc {
bool vis[MX], on[MX];

void DFS(int u, int fa = 0) {
    static bool fl = false;
    vis[u] = true;

    for (int v : G[u]) {
        if (not vis[v]) {
            DFS(v, u);

            if (fl) {
                break;
            }

            if (on[v]) {
                if (on[u]) {
                    fl = true;
                }

                on[u] = true;
                break;
            }
        } else if (v != fa) {
            on[u] = on[v] = true;
            break;
        }
    }
}

void DFS1(int u, int mn = INF) {
    static bool vis[MX], fl = false;
    static int to = -1;
    printf("%d ", u);
    vis[u] = true;
    std::sort(G[u].begin(), G[u].end());

    if (on[u] and not ~to) {
        fl = true;
        to = u;
    }

    int cnt = 0;

    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];

        if (not vis[v]) {
            if (on[u] and v > mn and fl and cnt == G[u].size() - 2) {
                fl = false;
                break;
            }

            if (not vis[v]) {
                DFS1(v, on[u] and
                     on[v] ? i < G[u].size() - 1 ? vis[G[u][i + 1]] ? i < G[u].size() - 2 ? G[u][i + 2] : mn : G[u][i + 1] : mn :
                     INF);
                cnt += not on[v];
            }
        }
    }
}

void solve() {
    DFS(1);
    DFS1(1);
}
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    for (int i = 1, u, v; i <= m; i++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    if (m == n - 1) {
        solveTree::DFS(1);
    } else {
        solveCyc::solve();
    }
}

算法标签

$DFS$、树的字典序遍历、单环图处理、贪心策略、邻接表排序

问题重述

给定 $n$ 个城市和 $m$ 条双向道路，图为树（$m=n-1$） 或单环图（$m=n$） ，且保证连通。要求找到一个访问所有城市的序列（仅记录首次到达的城市），使得序列的字典序最小。旅行规则：可从当前城市前往未访问的邻城，或沿首次访问的路径退回上一城市，最终需覆盖所有城市。

核心思路

图的结构决定了遍历策略：

1. 树结构（$m=n-1$）：无环，贪心选择当前节点的最小未访问邻城即可，无需回溯决策。
2. 单环图（$m=n$）：存在唯一环，需先定位环上节点，再在环上节点处做特殊决策——保证贪心选最小邻城的同时，不遗漏环上其他节点，避免因环的存在导致字典序变大。

代码详细解析

一、全局与输入处理

• 邻接表 $G[MX]$：存储图的连接关系，$MX$ 设为 $5010$ 适配 $n\le5\times10^3$ 的数据范围。
• main函数：读入 $n$ 和 $m$，构建无向图的邻接表；根据 $m$ 是 $n-1$ 还是 $n$，调用对应处理模块。

二、树的处理（solveTree命名空间）

核心逻辑

树无环，遍历过程中不会出现“选择分支后无法返回环上”的问题，因此直接用贪心 $DFS$：

1. 标记当前节点为已访问（$vis[u]=true$），并输出该节点（记录首次到达）。
2. 对当前节点的邻接表排序，保证优先遍历编号更小的节点。
3. 递归访问所有未访问的邻接节点，实现字典序最小的遍历。

代码详解

bool vis[MX];
void DFS(int u) {
    printf("%d ", u); // 记录首次到达
    vis[u] = true;
    std::sort(G[u].begin(), G[u].end()); // 贪心排序，优先选小数
    for (int v : G[u]) {
        if (not vis[v]) {
            DFS(v); // 递归访问未访问的最小邻城
        }
    }
}

三、单环图的处理（solveCyc命名空间）

单环图的关键是定位环上节点，再在环上节点处调整遍历顺序，避免错过更优路径。分为两步：找环 + 环上贪心遍历。

1. 找环（DFS函数）

• 目标：用 $on[]$ 数组标记环上所有节点。
• 逻辑：
  1. 递归遍历图，用 $vis[]$ 标记已访问节点，$fa$ 记录父节点。
  2. 遇到已访问且非父节点的节点（回边），说明找到环的起点和终点，标记这两个节点为环上节点（$on[u]=on[v]=true$）。
  3. 回溯时，若子节点在环上且当前节点未标记，则标记当前节点为环上节点，直到环的起点，完成整个环的标记。

2. 环上贪心遍历（DFS1函数）

• 目标：在环上节点处做决策，保证字典序最小，同时覆盖所有节点。
• 核心处理：
  1. 同样先输出当前节点，标记已访问，排序邻接表。
  2. 若当前节点是环上节点（$on[u]$），需判断是否跳过某些分支：避免因优先选小数导致环上其他节点无法访问。
  3. 递归访问邻接节点时，传递“最小限制值”，确保环上遍历不偏离字典序最小的路径。

3. 单环图入口（solve函数）

先调用 $DFS$ 找环，再调用 $DFS1$ 完成字典序最小遍历。

四、复杂度分析

• 时间复杂度：$O(n\log n)$。核心开销是邻接表排序，每个节点的邻接表排序时间为 $O(k\log k)$（$k$ 为邻接节点数），总排序时间为 $O(m\log k) \le O(n\log n)$（因 $m\le n$）。
• 空间复杂度：$O(n)$。邻接表、访问标记数组（$vis[]$）、环标记数组（$on[]$）均占用 $O(n)$ 空间。

关键注意点

1. 邻接表排序是贪心策略的基础，确保每次优先选择最小节点，是字典序最小的核心。
2. 单环图的环标记是关键：只有明确环上节点，才能在这些节点处调整遍历逻辑，避免因环导致的路径错误。
3. 树与单环图的区分处理：利用 $m=n-1$（树）和 $m=n$（单环图）的特性，针对性设计算法，提升效率。