代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 5000
struct node
{
    int u,v;
}a[MAXN+5];
int n,m;
int vis[MAXN+5],ans[MAXN+5],seq[MAXN+5],top;
vector<int> G[MAXN+5];
int Gr[MAXN+5][MAXN+5];
void dfs(int x)
{
    vis[x]=1;
    seq[++top]=x;
    for(int i=0;i<G[x].size();i++)
        {
            int xnt=G[x][i];
            if(vis[xnt]||!Gr[x][xnt])continue;
            dfs(xnt);
        }
}
int main()
{
//	freopen("travel.in","r",stdin);
//	freopen("travel.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)ans[i]=n+1;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        a[i].u=u,a[i].v=v;
        G[u].push_back(v);
        G[v].push_back(u);
        Gr[u][v]=1;
        Gr[v][u]=1;
    }
    for(int i=1;i<=n;i++)
    sort(G[i].begin(),G[i].end());
    if(n==m)
    for(int i=1;i<=m;i++)
    {
        top=0;
        for(int j=1;j<=n;j++)
        vis[j]=0;
        Gr[a[i].u][a[i].v]=0;
        Gr[a[i].v][a[i].u]=0;
        dfs(1);
        Gr[a[i].u][a[i].v]=1;
        Gr[a[i].v][a[i].u]=1;
        if(top<n)continue;
        int F=1;
        for(int j=1;j<=n;j++)
        if(ans[j]>seq[j])break;
        else if(ans[j]<seq[j]){F=0;break;}
        if(F)
        {
            for(int j=1;j<=n;j++)
            ans[j]=seq[j];
        }
    }
    else 
    {
        dfs(1);
        for(int i=1;i<=n;i++)
        ans[i]=seq[i];
    }
    for(int i=1;i<=n;i++)
    printf("%d ",ans[i]);
}

评测结果