代码

// luogu-judger-enable-o2
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<algorithm>
using namespace std;
const int MAX=1e4+5;
struct p{
    int x;
    bool operator< (const p &a)
    const{
        return x<a.x;
    }
};
struct q{
    int x,y;
}s[MAX];
int n,m,num,tot,s1,s2;
int h[MAX],ans[MAX],qu[MAX],Ans[MAX];
vector<p> c[MAX];
bool use[MAX];
bool look(int x,int y)
{
    if(s1==x&&s2==y) return 1;
    if(s1==y&&s2==x) return 1;
    return 0;
}
void Change()
{
    for(int i=1;i<=n;++i)
      if(Ans[i]&&Ans[i]<ans[i]) return;
      else if((Ans[i]&&Ans[i]>ans[i])||!Ans[i])
      {
      	for(int j=1;j<=n;++j)
      	  Ans[j]=ans[j];
      	return;
      }
}
void dfs(int x,int fa)
{
    int siz=c[x].size();
    use[x]=1,ans[++tot]=x;
    for(int i=0;i<siz;++i)
      if(c[x][i].x!=fa&&!use[c[x][i].x]&&!look(x,c[x][i].x)) dfs(c[x][i].x,x);
}
int main()
{
//	freopen("travel.in","r",stdin);
//	freopen("travel.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;++i)
      scanf("%d%d",&x,&y),c[x].push_back((p){y}),c[y].push_back((p){x}),s[i].x=x,s[i].y=y;
    for(int i=1;i<=n;++i)
      sort(c[i].begin(),c[i].end());
    if(m==n-1)
    {
        dfs(1,0);
        for(int i=1;i<=n;++i)
          printf("%d ",ans[i]);
    }
    else
    {
        for(int i=1;i<=m;++i)
          {
          	memset(use,0,sizeof(use));
          	s1=s[i].x,s2=s[i].y,tot=0;
          	dfs(1,0);
            if(tot==n) Change();
          }
        for(int i=1;i<=n;++i)
          printf("%d ",Ans[i]);
    }
    return 0;
}

评测结果