代码

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

#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 char *outp;
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[8192];

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];
static char *OUT;  /* output cursor under DuckInfo; unused under LOCAL */
static int outn;

/* radix sort directed edges by (u, v), 13 bits each */
static void sort_edges(void) {
  int i, e;
  for (i = 0; i < 8192; i++) cnt[i] = 0;
  for (e = 0; e < E2; e++) cnt[ev[e]]++;
  for (i = 1; i < 8192; i++) cnt[i] += cnt[i - 1];
  for (e = E2 - 1; e >= 0; e--) tmp2[--cnt[ev[e]]] = e;
  for (i = 0; i < 8192; i++) cnt[i] = 0;
  for (e = 0; e < E2; e++) cnt[eu[tmp2[e]]]++;
  for (i = 1; i < 8192; i++) cnt[i] += cnt[i - 1];
  for (e = E2 - 1; e >= 0; e--) ord[--cnt[eu[tmp2[e]]]] = tmp2[e];
  /* build CSR: adj[] holds sorted neighbors, head[u] start index */
  for (i = 1; i <= n; i++) head[i] = 0;
  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
   * (eparent is already visited; tail is included here). */
  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; /* fallback (unreachable: tail > c1) */
  }
  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;
        }
      }
    }
  }
  /* should not reach here, but fallback */
  brku = rtail; brkv = rhead;
}

static inline void wint(int x) {
  char tb[8];
  int len = 0;
  if (x == 0) tb[len++] = '0';
  while (x) { tb[len++] = (char)('0' + x % 10); x /= 10; }
  while (len) { *OUT++ = tb[--len]; }
}

static void dfs(int x) {
  int e;
  used[x] = 1;
  wint(x);
  *OUT++ = ' ';
  for (e = head[x]; e < head[x] + deg[x]; e++) {
    int y = adj[e];
    if (used[y]) continue;
    if ((x == brku && y == brkv) || (x == brkv && y == brku)) continue;
    dfs(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);
      /* reset vis for final dfs uses `used` (separate) */
      deal();
      dfs(1);
    }
    *(OUT - 1) = '\n';  /* replace trailing space with newline */
    *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();
  }
  /* print */
  {
    /* collect order via a manual stack-based dfs to avoid using OUT */
    static int stk[MAXN], sp;
    int order[MAXN], oc = 0;
    sp = 0; stk[sp++] = 1;
    used[1] = 1;
    while (sp) {
      int x = stk[--sp];
      order[oc++] = x;
      /* push neighbors in reverse sorted order so smallest visited first */
      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;
        stk[sp++] = y;
      }
    }
    for (i = 0; i < oc; i++) printf("%d%c", order[i], i + 1 < oc ? ' ' : '\n');
  }
  return 0;
}
#endif

评测结果