代码

/* NOIP2018 旅行 (noip18d) - base ring tree lexicographically smallest DFS order
 * Dual-mode: DuckInfo direct-memory IO (submission) / stdio (LOCAL for testing).
 */
#include <stdint.h>

static char *OUT;

#ifdef LOCAL
#include <stdio.h>
static inline int rd() { int x; scanf("%d", &x); return x; }
#else
#include <sys/auxv.h>
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 const char *inend;
static uint64_t *pout_size;
static inline int rd() {
  int x = 0;
  while (*inp < '0' || *inp > '9') inp++;
  while (*inp >= '0' && *inp <= '9') { x = x * 10 + (*inp - '0'); inp++; }
  return x;
}
#endif

#define MAXN 5005
#define MAXE 10010

static int n, m;
static int eu[MAXE], ev[MAXE];   /* directed edges */
static int E2;                   /* = 2*m */
static int deg[MAXN];
static int head[MAXN];
static int adj[MAXE];
static int ord[MAXE], tmp2[MAXE];
static int cnt[MAXN];

static char onring[MAXN];
static char vis[MAXN];      /* in-path for find_ring */
static int vstack[MAXN], vsp;
static int rstack[MAXN], rsp;
static int rhead, rtail;
static int brku, brkv;

static char used[MAXN];

/* radix sort directed edges by (u, v); values in [1,n] */
static void sort_edges(void) {
  int i, e, lim = n + 1;
  for (i = 0; i <= n; i++) cnt[i] = 0;
  for (e = 0; e < E2; e++) cnt[ev[e]]++;
  for (i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
  for (e = E2 - 1; e >= 0; e--) tmp2[--cnt[ev[e]]] = e;
  for (i = 0; i <= n; i++) cnt[i] = 0;
  for (e = 0; e < E2; e++) cnt[eu[tmp2[e]]]++;
  for (i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
  for (e = E2 - 1; e >= 0; e--) ord[--cnt[eu[tmp2[e]]]] = tmp2[e];
  {
    int prev = -1;
    for (e = 0; e < E2; e++) {
      int u = eu[ord[e]];
      if (u != prev) { head[u] = e; prev = u; }
      adj[e] = ev[ord[e]];
    }
  }
}

/* find ring; returns 1 when found */
static int find_ring(int x, int fa) {
  int e;
  if (vis[x]) {
    rhead = x;
    onring[x] = 1;
    rtail = vstack[vsp - 1];
    while (vstack[vsp - 1] != x) {
      onring[vstack[vsp - 1]] = 1;
      rstack[rsp++] = vstack[vsp - 1];
      vsp--;
    }
    return 1;
  }
  vis[x] = 1;
  vstack[vsp++] = x;
  for (e = head[x]; e < head[x] + deg[x]; e++) {
    int y = adj[e];
    if (y == fa) continue;
    if (find_ring(y, x)) return 1;
  }
  vsp--;
  vis[x] = 0;
  return 0;
}

/* decide the break edge */
static void deal(void) {
  int turn;
  int e = rhead;
  int c1 = rstack[rsp - 1];
  int eparent = (vsp >= 2) ? vstack[vsp - 2] : 0;
  /* turn[0] = smallest neighbor of entrance e that is > c1 and != eparent */
  turn = 0;
  {
    int idx;
    for (idx = head[e]; idx < head[e] + deg[e]; idx++) {
      int y = adj[idx];
      if (y > c1 && y != eparent) { turn = y; break; }
    }
    if (turn == 0) turn = rtail;
  }
  while (rsp > 0) {
    int x = rstack[--rsp];
    int i, d = deg[x];
    int nxt;
    if (x == rtail) { brku = x; brkv = rhead; return; }
    nxt = rstack[rsp - 1];
    {
      int last = adj[head[x] + d - 1];
      if (last > turn && last == nxt) { brku = x; brkv = nxt; return; }
      if (last != nxt && onring[last]) {
        int second = adj[head[x] + d - 2];
        if (second > turn && second == nxt) { brku = x; brkv = nxt; return; }
      }
      if (last != nxt && d > 2) {
        for (i = 0; i < d; i++) {
          if (adj[head[x] + i] == nxt) {
            if (onring[adj[head[x] + i + 1]]) {
              if (d - i > 2) turn = adj[head[x] + i + 2];
            } else {
              turn = adj[head[x] + i + 1];
            }
            break;
          }
        }
      }
    }
  }
  brku = rtail; brkv = rhead;
}

static inline void wint(int x) {
  char *p = OUT;
  if (x >= 1000) {
    int d = x / 1000; *p++ = (char)('0' + d); x -= d * 1000;
    d = x / 100; *p++ = (char)('0' + d); x -= d * 100;
    d = x / 10; *p++ = (char)('0' + d); x -= d * 10;
    *p++ = (char)('0' + x);
  } else if (x >= 100) {
    int d = x / 100; *p++ = (char)('0' + d); x -= d * 100;
    d = x / 10; *p++ = (char)('0' + d); x -= d * 10;
    *p++ = (char)('0' + x);
  } else if (x >= 10) {
    int d = x / 10; *p++ = (char)('0' + d); x -= d * 10;
    *p++ = (char)('0' + x);
  } else {
    *p++ = (char)('0' + x);
  }
  *p++ = ' ';
  OUT = p;
}

static void dfs(int start) {
  int sp = 0;
  vstack[sp++] = start;
  used[start] = 1;
  while (sp) {
    int x = vstack[--sp];
    int e;
    wint(x);
    for (e = head[x] + deg[x] - 1; e >= head[x]; e--) {
      int y = adj[e];
      if (used[y]) continue;
      if ((x == brku && y == brkv) || (x == brkv && y == brku)) continue;
      used[y] = 1;
      vstack[sp++] = y;
    }
  }
}

#ifndef LOCAL
int main(void) {
  struct DuckInfo *d = (struct DuckInfo *)getauxval(0x6b637564);
  inp = d->stdin_ptr;
  inend = d->stdin_ptr + d->stdin_size;
  OUT = d->stdout_ptr;
  pout_size = &d->stdout_size;
  {
    int i;
    n = rd(); m = rd();
    E2 = 0;
    for (i = 1; i <= n; i++) deg[i] = 0;
    for (i = 0; i < m; i++) {
      int u = rd(), v = rd();
      eu[E2] = u; ev[E2] = v; E2++;
      eu[E2] = v; ev[E2] = u; E2++;
      deg[u]++; deg[v]++;
    }
    sort_edges();
    if (m == n - 1) {
      brku = brkv = 0;
      dfs(1);
    } else {
      find_ring(1, 1);
      deal();
      dfs(1);
    }
    *(OUT - 1) = '\n';
    *pout_size = (uint64_t)(OUT - d->stdout_ptr);
  }
  __asm__ volatile("mov $60,%eax; xor %edi,%edi; syscall");
  __builtin_unreachable();
}
#else
int main(void) {
  int i;
  n = rd(); m = rd();
  E2 = 0;
  for (i = 1; i <= n; i++) deg[i] = 0;
  for (i = 0; i < m; i++) {
    int u = rd(), v = rd();
    eu[E2] = u; ev[E2] = v; E2++;
    eu[E2] = v; ev[E2] = u; E2++;
    deg[u]++; deg[v]++;
  }
  sort_edges();
  if (m == n - 1) {
    brku = brkv = 0;
  } else {
    find_ring(1, 1);
    deal();
  }
  {
    static int order[MAXN]; int oc = 0;
    int sp = 0;
    vstack[sp++] = 1; used[1] = 1;
    while (sp) {
      int x = vstack[--sp];
      order[oc++] = x;
      for (i = head[x] + deg[x] - 1; i >= head[x]; i--) {
        int y = adj[i];
        if (used[y]) continue;
        if ((x == brku && y == brkv) || (x == brkv && y == brku)) continue;
        used[y] = 1;
        vstack[sp++] = y;
      }
    }
    for (i = 0; i < oc; i++) printf("%d%c", order[i], i + 1 < oc ? ' ' : '\n');
  }
  return 0;
}
#endif

评测结果