任意选定一个城市作为起点,然后从起点开始,每次可 以选择一条与当前城市相连的道路,走向一个没有去过的城市,或者沿着第一次访问该 城市时经过的道路后退到上一个城市。当回到起点时,可以选择结束这次旅行或 继续旅行。注意每个城市都被访问到。(m<=n)
每到达一个新的城市(包括起点)时,将 它的编号记录下来。这样会形成一个长度为 n的序列。现在希望这个序列的字典序 最小
m<n ,贪心,从1开始,每次选序号最小的下一个点
m==n时,是基环树,直接枚举所删的边,变为一颗树,然后同(1)
#include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std ; const int N=5002,M=N; int n,m; namespace A{ int vis[N]; int e[N*2],tot; vector<int> g[N]; vector<int>ans; int re; void add(int x,int y){ e[++tot]=y; g[x].push_back(tot); } int cmp(int x,int y){ return e[x]<=e[y]; } void dp(int x,int fa){ ans.push_back(x); int i,y; sort(g[x].begin(),g[x].end(),cmp); for(i=0;i<(int)g[x].size();i++){ y=e[g[x][i]]; if(y==fa) continue; dp(y,x); } } void solve(){ int i,x,y; for(i=1;i<=m;i++) cin>>x>>y,add(x,y),add(y,x); dp(1,0); for(i=0;i<(int)ans.size();i++) cout<<ans[i]<<' '; } }; namespace B{ int tot; struct T{ int x,y; }e[N*2]; int vis[N]; int qx,qy; vector<int>cir,A,ans; vector<int> g[N]; void add(int x,int y){ e[++tot].x=x,e[tot].y=y; g[x].push_back(tot); } int cmp(int x,int y){ return e[x].y<=e[y].y; } void dp(int x,int fa){ int i,y; if(vis[x]) return; A.push_back(x); vis[x]=1; for(i=0;i<g[x].size();i++){ y=e[g[x][i]].y; if(y==fa||(x==qx&&y==qy)||(x==qy&&y==qx)) continue; dp(y,x); } } void save(){ ans.clear(); for(int i=0;i<A.size();i++) ans.push_back(A[i]); } int chk(){ for(int i=0;i<(int)A.size();i++){ if(ans[i]==A[i]) continue; if(A[i]>ans[i]) return 0; else return 1; } } void upd(){ if(A.size()<n) return; if(ans.size()==0) save(); else if(chk()) save(); } void solve(){ int i,x,y; for(i=1;i<=m;i++) cin>>x>>y,add(x,y),add(y,x); for(i=1;i<=n;i++) sort(g[x].begin(),g[x].end(),cmp); for(i=1;i<=tot;i+=2){ A.clear(); memset(vis,0,sizeof vis); qx=e[i].x,qy=e[i].y; dp(1,-1); upd(); } for(i=0;i<ans.size();i++) cout<<ans[i]<<' '; } }; int main(){ cin>>n>>m; if(n==m) B::solve(); else A::solve(); }
标签:return,int,luogu,void,5022,tot,add,include From: https://www.cnblogs.com/towboa/p/16858421.html