代码

#include<bits/stdc++.h>
using namespace std;
 
int n, m, hea[505000], to[1001000], ban1=-1, ban2=-1;
int ui[505000], vi[505000], ans[505000], st[505000], tp, win;
 
void dfs(int x,int fff){
  st[++tp]=x;
  if (win==0&&st[tp]!=ans[tp]){
    win=st[tp]<ans[tp]? 1: -1;
  }
  if (win==-1) return;
  for (int i=hea[x];i<hea[x+1];++i)
    if (to[i]!=fff&&i!=ban1&&i!=ban2){
      dfs(to[i],x);
    }
}
 
void realmain(){
  tp=0; win=0;
  dfs(1,0);
  if (win==1) memcpy(ans,st,sizeof ans);
}
 
void BAN(int u,int v){
  ban1=lower_bound(to+hea[u],to+hea[u+1],v)-to;
  ban2=lower_bound(to+hea[v],to+hea[v+1],u)-to;
}
 
int usd[505000], cir[505000], tot, fa[505000], dep[505000];
void getcir(int x,int fff){
  usd[x]=1;
  dep[x]=dep[fff]+1; fa[x]=fff;
  for (int i=hea[x];i<hea[x+1];++i){
    int y=to[i]; if (y==fff) continue;
    if (!usd[y]) getcir(y,x);
    else if (dep[x]>dep[y]){
      for (int t=x;t!=y;t=fa[t])
    cir[tot++]=t;
      cir[tot++]=y;
    }
  }
}
 
int main(){
  cin>>n>>m; int u, v; if (max(n,m)>5e5) return 0; 
  for (int i=1;i<=m;++i){
    scanf("%d%d",&u,&v);
    ++hea[u]; ++hea[v];
    ui[i]=u; vi[i]=v;
  }
  for (int i=1;i<=n+1;++i) hea[i]+=hea[i-1];
  for (int i=1;i<=m;++i){
    u=ui[i]; v=vi[i];
    to[--hea[u]]=v;
    to[--hea[v]]=u;
  }
  for (int i=1;i<=n;++i)
    sort(to+hea[i],to+hea[i+1]);
  memset(ans,33,sizeof ans);
  if (m==n-1) realmain();
  else{
    getcir(1,0);
    for (int i=0;i<tot;++i){
      BAN(cir[i],cir[(i+1)%tot]);
      realmain();
    }
  }
  for (int i=1;i<=n;++i) printf("%d ",ans[i]);
}

评测结果