\(\text{Solution:}\)
首先题目描述有一点不准确：回头是必须要走完一条路无路可走的时候才能返回。
对于树的情况：显然贪心做就完事了。
对于基环树的情况：对于一个\(n\)条边的环，如果我们已经走了\(n-1\)条边，那么此时我们已经可以到达环上任意一点了。所以我们可以枚举并删边。
题目中要求一个点除非回溯否则不能再次访问，这意味着一定有一条边无法访问，枚举那一条边即可。
时间复杂度\(O(n^2).\)
#include<bits/stdc++.h>
using namespace std;
const int inf=(1<<30);
int n,m,E[5001][2];
vector<int>G[5001];
namespace P1{
vector<int>ans;
void dfs(int x,int y){
ans.push_back(x);
for(int i=0;i<G[x].size();++i){
int j=G[x][i];
if(j==y)continue;
dfs(j,x);
}
}
void solve(){
dfs(1,0);
for(int i=0;i<ans.size();++i)printf("%d ",ans[i]);
puts("");
}
}
namespace P2{
vector<int>ans,res;
bitset<5001>vis;
int Dv,Du;
void dfs(int x,int fa){
res.push_back(x);vis[x]=1;
for(int i=0;i<G[x].size();++i){
int j=G[x][i];
if((x==Du&&j==Dv)||(x==Dv&&j==Du)||vis[j]||j==fa)continue;
dfs(j,x);
}
}
inline bool check(){
for(int i=0;i<n;++i){
if(ans[i]!=res[i]){
if(ans[i]>res[i])return false;
return true;
}
}
return true;
}
void solve(){
for(int i=0;i<n;++i)ans.push_back(inf),res.push_back(0);
for(int i=1;i<=m;++i){
res.clear();vis.reset();
Du=E[i][0],Dv=E[i][1];
dfs(1,0);
for(;(int)res.size()<n;)res.push_back(inf);
if(!check())swap(res,ans);
}
for(int i=0;i<n;++i)printf("%d ",ans[i]);
puts("");
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int x,y;
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
E[i][0]=x,E[i][1]=y;
}
for(int i=1;i<=n;++i)sort(G[i].begin(),G[i].end());
if(m==n-1){P1::solve();return 0;}
P2::solve();
return 0;
}