思路

对于n=m的情况，一定存在一条环，枚举删除环上任意边，就变成树，只需对树做一个贪心搜索就可以找到字典序最小的序列。

时间复杂度

$O((n+m)*n)$

C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int N=50010;
vector<int> g[N];
int n,m,delv,delu,cir[N],tot,k;
int vis[N],sk[N];
vector<int> nper,per;
bool success=0;
bool dfs(int u){
    nper.push_back(u);
    if(success==0&&per.size()!=0&&nper[nper.size()-1]>per[nper.size()-1]) {
        return true;
    }
    else if(per.size()!=0&&nper[nper.size()-1]<per[nper.size()-1]) success=1;
    vis[u]=1;
    vector<int> ver;
    for(auto v:g[u]){
        if((u==delv&&v==delu)||(v==delv&&u==delu)||vis[v]) continue;
        if(dfs(v)) return true;
    }
    return false;
}
vector<pair<int,int>> edge;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        edge.push_back({u,v});
    }
    for(int i=1;i<=n;++i){
        sort(g[i].begin(),g[i].end());
    }
    if(n==m+1){
        dfs(1);
        for(int i=0;i<n;++i) cout<<nper[i]<<" ";
    }
    else {
        for(int i=0;i<m;++i){
            for(int j=1;j<=n;++j) vis[j]=0;
            delu=edge[i].first;
            delv=edge[i].second;
            tot=0;
            nper.clear();
            success=0;
            if(dfs(1)) continue;
            bool su=0;
            if(nper.size()<n) continue;
            else if(per.size()==0) per=nper;
            else {
                for(int j=0;j<n;++j){
                    if(nper[j]<per[j]) {
                        su=1;
                        break;
                    }
                    else if(nper[j]>per[j]) break;
                }
                if(su){
                    per=nper;
                }
            }
        }
        for(int i=0;i<per.size();++i) cout<<per[i]<<" ";
    }
    return 0;
}