算法

对于一棵树的情况, dfs + 贪心选取显然是正确的
对于基环树的情况
我们观察到城市不能重复行走
所以长为 \(L\) 的环最多只会被访问 \(L - 1\) 条边
枚举断边, 再跑 dfs + 贪心即可

代码

#include <bits/stdc++.h>
const int MAXN = 5e3 + 20;

int n, m;
std::vector<int> e[MAXN], ans;

int U[MAXN], V[MAXN];

class Subtast_1
{
private:

public:
    bool vis[MAXN];
    int res[MAXN];
    void dfs(int u)
    {
        ans.push_back(u), vis[u] = true;
        for (int i = 0; i < e[u].size(); ++i)
        {
            int v = e[u][i];
            if (!vis[v])
                dfs(v);
        }
    }

    void solve()
    {
        dfs(1);
        for (int i = 0; i < ans.size(); ++i)
            std::cout << ans[i] << " ";
    }
} s1;

class Subtask_2
{
private:

public:
    int res[MAXN], ans[MAXN];
    bool cmp()
    {
        for (int i = 1; i <= n; ++i)
            if (res[i] < ans[i])
                return true;
            else if (res[i] > ans[i])
                return false;
        return false;
    }

    int Delete_u, Delete_v, Past_Cnt = 0;
    bool NotbeDelete(int u, int v)
    {
        if ((u == Delete_u && v == Delete_v) || (u == Delete_v && v == Delete_u))
            return false;
        return true;
    }

    bool vis[MAXN];
    void dfs(int u)
    {
        vis[u] = true, res[++Past_Cnt] = u;
        for (int i = 0; i < e[u].size(); ++i) {
            int v = e[u][i];
            /*不跑删边*/
            if (!vis[v] && NotbeDelete(u, v))
                dfs(v);
        }
    }

    void solve()
    {
        for (int i = 1; i <= m; ++i)
        {
            int u = U[i], v = V[i];

            memset(res, 0, sizeof(res));
            memset(vis, false, sizeof(vis));
            Past_Cnt = 0;
            Delete_u = u, Delete_v = v;

            /*判断删掉的这条边在不在环上*/
            dfs(1);
            if (Past_Cnt < n)
                continue;

            bool Best = cmp();
            if (ans[1] == 0 || Best)
                memcpy(ans, res, sizeof(res));
        }

        for (int i = 1; i <= n; ++i)
            std::cout << ans[i] << " ";
    }
} s2;
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1, u, v; i <= m; ++i) {
        scanf("%d %d", &u, &v);
        e[u].push_back(v), e[v].push_back(u), U[i] = u, V[i] = v;
    }
    for (int i = 1; i <= n; ++i)
        sort(e[i].begin(), e[i].end());

    if (m == n - 1)
        s1.solve();
    else if (m == n)
        s2.solve();

    return 0;
}

总结

断边后, 基环树可按照树的方式处理