原题链接
题意：
一棵树，从1出发，每到达一个新的点就记录下编号。求一种走法使得记录下来的编号字典序最小。
思路：
题意里说m<=n，就说明这棵树可能是基环树。
如果这棵树是普通的树的话，直接排序后dfs一下，每次都走字典序最小的点。如果这棵树是基环树的话，首先要明确一个性质，环上肯定有一条边是不经过的，可以手动模拟一下过程。所以我们就可以每次枚举这条不经过的边，求答案后取字典序最小。这条边不经过的话，对答案是无影响的，可以确保正确性。
复杂度大概n*n，吸吸氧气就能过。
代码：
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; }
