题解：P5049 [NOIP 2018 提高组] 旅行 加强版

· · 题解

:::info[题目大意] 给出一个 n 个点 m 条边的无向图（m\le n），保证图连通、没有重边和自环。

从任意一点出发，每次可以沿边走向一个未遍历过的点或沿来时边回到上一个点，要求遍历完整个图。将每次到达未遍历过的点的编号按顺序记下成一个序列，求所有可能的序列中字典序最小的。

思路

这里有个很重要的条件：m\le n（但是我第一眼看题没有注意到，想了好久），且图连通，这意味着图要么是一棵树，要么是一棵基环树。

要求字典序最小就是一种显然的贪心思路：在合法条件下，每次一定是先走编号最小的点。所以，我们一定是从 1 点出发的。

进一步，我们分开图的两种形态考虑。

树

因为每次只能沿边到新点或者回溯到旧点，所以到达一点时必须要把以该点为根的子树全部走完才能回溯（若提前回溯则无法再次到达该点，也就没有机会再走其子树）。

结合贪心思路，我们直接将每个节点连出的点排序，从小到大依次走即可。

基环树

入环前和出环后一切同上，变化在环上。

直接说结论：第一次走到环上的点时，正常跑，到接下来第二个环上的点时至回溯前产生变化。变化的走法可以在跑完非环连出点后直接进行回溯而不继续往环上跑，等待走环的另一边。

注意到只有当环上连出点是所有连出点中编号最大的（同树：因为肯定是要走完非环连出点及其子树才能回溯，所以把环上连出点的位置替换为更大的连出点形成的最终序列一定更劣），且大于回溯后将要走的点时，才会走完非环连出点直接回溯。

做法

思路捋清了代码也不难写，我写的是两个不同的搜索，对应两种走法按照上述方法直接转换即可。

但是我为什么总是忘记怎么写判环（写的很丑）啊！ :::success[代码]

#include <bits/stdc++.h>
std::mt19937_64 RNG(time(0));
#define randint(l, r)\
(std::uniform_int_distribution<long long>((l),(r))(RNG))
namespace xuan_never {
using namespace std;
typedef long long ll;
// #define int long long
const int maxn = 5e5 + 50;
int n, m;
vector<int> G[maxn];
bool onl[maxn], vis[maxn];
int anl[maxn], top = 0;
int fa[maxn], dep[maxn], L1, L2;
void dfs1(int u) {
    vis[u] = 1, dep[u] = dep[fa[u]] + 1;
    for (int v : G[u]) {
        if (v == fa[u]) continue;
        if (vis[v])
            L1 = v, L2 = u;
        else fa[v] = u, dfs1(v);
    }
}
void get_loop() {
    dfs1(1);
    if (dep[L1] < dep[L2]) swap(L1, L2);
    while (dep[L1] > dep[L2])
        onl[L1] = 1, L1 = fa[L1];
    while (L1 ^ L2)
        onl[L1] = 1, onl[L2] = 1,
        L1 = fa[L1], L2 = fa[L2];
    onl[L1] = 1;
    memset(vis, 0, (n + 5) * sizeof(bool));
}
void solve2(int u, int ot);
void solve1(int u) {
    vis[u] = 1;
    anl[++top] = u;
    sort(G[u].begin(), G[u].end());
    if (u == L1) {
        int o1 = 0;
        for (int i = 0, v; i < G[u].size(); ++i) {
            if (vis[v = G[u][i]]) continue;
            if (onl[v] && !o1) {
                o1 = v;
                solve2(v, G[u][i + 1]);
                continue;
            }
            solve1(v);
        }
        return;
    }
    for (int v : G[u]) {
        if (vis[v]) continue;
        solve1(v);
    }
}
void solve2(int u, int ot) {
    vis[u] = 1;
    anl[++top] = u;
    sort(G[u].begin(), G[u].end());
    int to = 0, ba = 0;
    for (int v : G[u]) {
        if (vis[v]) continue;
        if (onl[v]) to = v;
        ba = v;
    }
    if (ba == to && to > ot) {
        for (int v : G[u]) {
            if (vis[v] || onl[v]) continue;
            solve1(v);
        }
        return;
    }
    for (int i = 0, v; i < G[u].size(); ++i) {
        if (vis[v = G[u][i]]) continue;
        if (onl[v]) {
            int nx = 0;
            for (int j = i + 1; j < G[u].size() && !nx; ++j)
                if (!vis[G[u][j]]) nx = G[u][j];
            solve2(v, nx ? nx : ot);
        } else solve1(v);
    }
}
void init() {}
void mian() {
    init();
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; ++i) {
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    if (n == m) get_loop();
    solve1(1);
    for (int i = 1; i <= n; ++i)
        cout << anl[i] << ' ';
    cout << '\n';
}
#undef int
} using namespace xuan_never;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false), cout.tie(nullptr);
//  init();
    int T = 1;
//  cin >> T;
    while (T--) mian();
    return 0;
}

:::