外贸企业公司网站建设/厦门人才网招聘最新信息

题目传送门

题目大意： 现在有一棵树或一张只有一个环的图（连通），要求遍历一遍这个图，遍历的顺序即为一个长度为 $n$ 的序列，要求字典序最小的序列。

题解

假如是一棵树的话，显然贪心即可，从 $1$ 出发，每次往编号小的走就好了。

假如只是多一条边的话，枚举删掉那一条边，然后变成一棵树来做。

因为每次都要往编号小的走，所以我把当前点能到达的点都弄起来，然后 $sort$ 一下编号，因为大量使用 $sort$，所以不开 $O2$ 过不了……

代码如下：

#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;
#define maxn 5010struct edge{int x,y;};
edge edges[maxn];
int n,m;
bool v[maxn];
bool check(int *a,int *b)
{for(int i=1;i<=n;i++)if(a[i]<b[i])return true;else if(a[i]>b[i]) return false;return false;
}
int a[maxn],t;
int ans[maxn];
bool tf[maxn];
struct nod{int y,next;};
nod e[2*maxn];
int zhan[maxn],tt=0;
int len;
int first[maxn];
void dfs(int x)
{a[++t]=x;tf[x]=true;if(t==n)return;int st=tt+1;for(int i=first[x];i;i=e[i].next){int y=e[i].y;if(tf[y])continue;zhan[++tt]=y;}if(st==tt+1)return;sort(zhan+st,zhan+tt+1);int ed=tt;for(int i=st;i<=ed;i++)if(!tf[zhan[i]])dfs(zhan[i]);
}
void buildroad(int x,int y)
{e[++len]=(nod){y,first[x]};first[x]=len;
}
void work()
{len=0;for(int i=1;i<=n;i++)tf[i]=false,first[i]=0;for(int i=1;i<=m;i++)if(!v[i])buildroad(edges[i].x,edges[i].y),buildroad(edges[i].y,edges[i].x);t=tt=0;dfs(1);
}int main()
{scanf("%d %d",&n,&m);for(int i=1;i<=m;i++)scanf("%d %d",&edges[i].x,&edges[i].y);if(m==n-1){work();for(int i=1;i<=n;i++)printf("%d ",a[i]);return 0;}for(int i=1;i<=n;i++)//别忘了初始化ans数组ans[i]=999999999;for(int i=1;i<=m;i++){v[i]=true;//删掉第i条边work();if(t==n&&check(a,ans)){for(int j=1;j<=n;j++)ans[j]=a[j];}v[i]=false;}for(int i=1;i<=n;i++)printf("%d ",ans[i]);
}