题目戳我

\(\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;
}