代码

#include<cstdio>
#include<cstring>
#include<queue>
bool isin[5555];
int n,m;
struct edge
{int p,t;bool flag;}e[22222];
int asw[5555],tot,h[5555];
inline void build(int x,int y)
{e[++tot]=(edge){h[x],y,0},h[x]=tot;}
int low,from[5555],d[5555];
int tp,stk[5555];
bool vis[5555];
int argv[5555][5555];
int argc[5555];
bool flag[5555][5555];
std::priority_queue<int>Q;
inline int dfs(int s=1,bool need=1)
{
    stk[++tp]=s;
    if(stk[tp]<asw[tp])need=0;
    if(need&&(stk[tp]>asw[tp]))return 0;
    vis[s]=1;
    for(register int i=1;i<=argc[s];i++)
    {
        int to=argv[s][i];
        if(flag[s][to])continue;
        if(vis[to])continue;
        int t=dfs(to,need);
        if(!t)return 0;
        else if(t==2)need=0;
    }if(!need)return 2;
    else return 1;
}
int x[5555],y[5555];
inline void cnter()
{
    register int i,ii,iii;
    for(i=1;i<=n;i++)
    {
        for(ii=h[i];ii;ii=e[ii].p)
        {
            int to=e[ii].t;
            Q.push(-to);
        }
        for(;Q.size();)
        {argv[i][++argc[i]]=-Q.top();Q.pop();}
    }
    asw[1]=2;
    if(m==n-1)
    {
        dfs();
        for(i=1;i<=n;i++)
            asw[i]=stk[i];
    }
    else
    {
        for(i=1;i<=m;i++)
        {
            tp=0;
            flag[x[i]][y[i]]=flag[y[i]][x[i]]=1;
            memset(vis,0,sizeof(vis));
            dfs();
            if(tp==n)
            {
                for(ii=1;ii<=n;ii++)
                {
                    if(asw[ii]>stk[ii])
                    {
                        for(iii=1;iii<=n;iii++)
                            asw[iii]=stk[iii];
                        break;
                    }
                    else if(asw[ii]<stk[ii])break;
                }
            }
            flag[x[i]][y[i]]=flag[y[i]][x[i]]=0;
        }
    }
    for(i=1;i<n;i++)
        printf("%d ",asw[i]);
    printf("%d\n",asw[n]);
}
int main()
{
    register int i;
    scanf("%d%d",&n,&m);
    isin[1]=1;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        d[x[i]]++,d[y[i]]++;
        build(x[i],y[i]),build(y[i],x[i]);
    }
    cnter();
}

评测结果