代码

// NOIP2018 旅行 加强版 (duck.ac 2002) - optimized
#include <sys/auxv.h>
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#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;
#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];int i=0;do{tmp[i++]=(char)('0'+x%10);x/=10;}while(x);while(i)*outp++=tmp[--i];*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();
  if(n==1){ put_int(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");
#endif
  }
  int em=2*m;
  int *eu=(int*)malloc((size_t)em*sizeof(int));
  int *ev=(int*)malloc((size_t)em*sizeof(int));
  int *etu=(int*)malloc((size_t)em*sizeof(int));
  int *etv=(int*)malloc((size_t)em*sizeof(int));
  int *cnt=(int*)malloc((size_t)(n+2)*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]++;}

  memset(cnt,0,(size_t)(n+2)*sizeof(int));
  for(int i=0;i<em;i++)cnt[ev[i]]++;
  for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
  for(int i=em-1;i>=0;i--){int c=--cnt[ev[i]];etu[c]=eu[i];etv[c]=ev[i];}
  memset(cnt,0,(size_t)(n+2)*sizeof(int));
  for(int i=0;i<em;i++)cnt[etu[i]]++;
  for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
  for(int i=em-1;i>=0;i--){int c=--cnt[etu[i]];eu[c]=etu[i];ev[c]=etv[i];}

  start[1]=0;
  for(int i=1;i<=n;i++)start[i+1]=start[i]+deg[i];

  // 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=ev[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[ev[idx]]) idx++;
    if(idx>=e){top--;continue;}
    int tt=ev[idx];
    if(oncycle[x]){
      int j=idx+1; while(j<e&&vis[ev[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?ev[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
}

评测结果