洛谷P5022 旅行（基環樹+斷環法）

const int maxn=2e5+100;
int h[maxn],idx;
struct node{
    int u,v,ne;
}edge[maxn*2];
int n,m;
vector<int>g[maxn];

void add(int u,int v){
    edge[idx]={u,v,h[u]};h[u]=idx++;
}

int timetmp=0;
int res[maxn],tmp[maxn],vis[maxn];

void dfs(int u,int fa,int delu,int delv,int tmp[]){
    if(vis[u]) return ;
    vis[u]=1;
    tmp[++timetmp]=u;
    for(int i=0;i<g[u].size();i++){
        int t=g[u][i];
        if(t==fa) continue;
        if(t==delu&&u==delv) continue;///目前邊是本次删除的邊
        if(t==delv&&u==delu) continue;
        dfs(t,u,delu,delv,tmp);
    }
}

bool check(){
    for(int i=1;i<=n;i++)
        if(res[i]<tmp[i]) return 0;
        else if(res[i]>tmp[i]) return 1;//需要更改
}

int main(){
    memset(h,-1,sizeof h);
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        add(u,v);add(v,u);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());///對每個點的出邊進行排序
    if(n==m){///基環樹
        for(int i=0;i<idx;i+=2){///枚舉删哪條邊
            timetmp=0;
            memset(vis,0,sizeof vis);
            dfs(1,-1,edge[i].u,edge[i].v,tmp);
            if(timetmp<n) continue;///走不到所有的點
            if(res[1]==0||check()){
                for(int j=1;j<=n;j++) res[j]=tmp[j];///未被更新或是目前走法的字典序更小
            }
        }
    }
    else dfs(1,-1,-1,-1,res);
    for(int i=1;i<=n;i++) printf("%d ",res[i]);
    return 0;
}