代码

// v3: CSR build (single-pass fill) + per-node sort
#include <sys/auxv.h>
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#ifdef LOCAL
#include <stdio.h>
#endif
struct DuckInfo { uint64_t abi_version; const char *stdin_ptr; uint64_t stdin_size; char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size; char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size; const char *IB_ptr; uint64_t IB_limit; char *OB_ptr; uint64_t OB_limit; uint64_t tsc_frequency; } __attribute__((packed));
static const char *inp; static char *outp; static char *sbase;
static const char D2[] = "00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899";
#ifdef LOCAL
static char ibuf[1<<22]; static char obuf[1<<22];
#endif
static inline int rd(){int x=0;char c=*inp++;while(c<'0')c=*inp++;while(c>='0'){x=x*10+(c-'0');c=*inp++;}return x;}
static inline void put_int(int x,char sep){char tmp[8];char*p=tmp;do{int r=x%100;x/=100;*p++=D2[r*2+1];*p++=D2[r*2];}while(x>0);if(p[-1]=='0')p--;while(p>tmp)*outp++=*--p;*outp++=sep;}

int main(){
#ifdef LOCAL
  size_t _n=fread(ibuf,1,sizeof(ibuf),stdin); inp=ibuf; outp=obuf; sbase=obuf; (void)_n;
#else
  struct DuckInfo *di=(struct DuckInfo*)getauxval(0x6b637564);
  inp=di->stdin_ptr; outp=di->stdout_ptr; sbase=di->stdout_ptr;
#endif
  int n=rd(), m=rd();
  int em=2*m;
  int *eu=(int*)malloc((size_t)em*sizeof(int));
  int *ev=(int*)malloc((size_t)em*sizeof(int));
  int *csr=(int*)malloc((size_t)em*sizeof(int));
  int *cur=(int*)malloc((size_t)(n+1)*sizeof(int));
  int *deg=(int*)malloc((size_t)(n+1)*sizeof(int));
  int *start=(int*)malloc((size_t)(n+2)*sizeof(int));
  int *deg2=(int*)malloc((size_t)(n+1)*sizeof(int));
  unsigned char *oncycle=(unsigned char*)malloc((size_t)(n+1));
  unsigned char *vis=(unsigned char*)malloc((size_t)(n+1));
  int *queue=(int*)malloc((size_t)(n+1)*sizeof(int));
  int *sx=(int*)malloc((size_t)(n+1)*sizeof(int));
  int *si=(int*)malloc((size_t)(n+1)*sizeof(int));
  int *sn=(int*)malloc((size_t)(n+1)*sizeof(int));

  memset(deg,0,(size_t)(n+1)*sizeof(int));
  for(int i=0;i<m;i++){int u=rd(),v=rd();eu[2*i]=u;ev[2*i]=v;eu[2*i+1]=v;ev[2*i+1]=u;deg[u]++;deg[v]++;}

  start[1]=0;
  for(int i=1;i<=n;i++)start[i+1]=start[i]+deg[i];
  memcpy(cur,start,(size_t)(n+1)*sizeof(int));
  for(int i=0;i<em;i++){int u=eu[i];csr[cur[u]++]=ev[i];}

  // per-node sort
  for(int i=1;i<=n;i++){
    int s=start[i], d=deg[i];
    if(d==2){ if(csr[s]>csr[s+1]){int t=csr[s];csr[s]=csr[s+1];csr[s+1]=t;} }
    else if(d>2){
      int e=s+d;
      if(d<=16){ for(int a=s+1;a<e;a++){int x=csr[a];int b=a-1;while(b>=s&&csr[b]>x){csr[b+1]=csr[b];b--;}csr[b+1]=x;} }
      else std::sort(csr+s,csr+e);
    }
  }

  // degree peeling
  memcpy(deg2,deg,(size_t)(n+1)*sizeof(int));
  memset(oncycle,1,(size_t)(n+1));
  int qh=0,qt=0;
  for(int i=1;i<=n;i++)if(deg2[i]<=1)queue[qt++]=i;
  while(qh<qt){int u=queue[qh++];if(!oncycle[u])continue;oncycle[u]=0;
    int s=start[u],e=start[u+1];
    for(int k=s;k<e;k++){int v=csr[k];if(oncycle[v]){if(--deg2[v]==1)queue[qt++]=v;}}}

  // greedy DFS
  memset(vis,0,(size_t)(n+1));
  vis[1]=1; put_int(1,' ');
  int top=0; sx[top]=1; si[top]=start[1]; sn[top]=0x7fffffff; top++;
  int turned=0;
  while(top>0){
    int x=sx[top-1], idx=si[top-1], now=sn[top-1];
    int e=start[x+1];
    while(idx<e && vis[csr[idx]]) idx++;
    if(idx>=e){top--;continue;}
    int tt=csr[idx];
    if(oncycle[x]){
      int j=idx+1; while(j<e&&vis[csr[j]])j++;
      int has_next=(j<e);
      if(!turned && oncycle[tt] && !has_next && now<tt){turned=1;top--;continue;}
      vis[tt]=1; put_int(tt,' ');
      si[top-1]=j;
      int child_now=has_next?csr[j]:now;
      sx[top]=tt; si[top]=start[tt]; sn[top]=child_now; top++;
    } else {
      vis[tt]=1; put_int(tt,' ');
      si[top-1]=idx+1;
      sx[top]=tt; si[top]=start[tt]; sn[top]=now; top++;
    }
  }

  outp[-1]='\n';
#ifdef LOCAL
  fwrite(obuf,1,(size_t)(outp-obuf),stdout); return 0;
#else
  di->stdout_size=(uint64_t)(outp-sbase);
  __asm__ volatile("syscall" : : "a"(60),"D"(0) : "rcx","r11","memory");
  return 0;
#endif
}

评测结果