代码

#include<algorithm>
#include<cstdio>
#include<vector>

const int N = 7e5 + 7;
const int inf = 1e9 + 7;
inline int read() {
    char ch = getchar();
    int ret = 0, f = 1;
    while (ch > '9' || ch < '0') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        ret = ret * 10 + ch - '0', ch = getchar();
    return ret * f;
}
int last[N], cnt, root;
struct Edge {
  int next, to;
} e[N * 2];
inline void add (int u, int v) {
  e[++cnt].next = last[u], e[cnt].to = v, last[u] = cnt;
}

int stack[N], vis[N], cNode[N], backNode;
int top = 0;
inline int find_circle (int x, int fa) {
  vis[x] = 1;
  for (int i = last[x]; i; i = e[i].next) {
    int to = e[i].to;
    if (to == fa) continue;
    if (vis[to]) {
      cNode[to] = cNode[x] = 1;
      backNode = to;
      return 1;
    }
    int oncircle = find_circle (to, x);
    if (oncircle && to != backNode) {
      cNode[x] = 1;
      return 1;
    }
  }

  return 0;
}

int idx[N], flag = 0;
int tot = 0;
int f[N];
std :: vector<int> xNode[N];


inline void work2 (register int x, int fa) {
    if (vis[x]) return ;
  idx[++cnt] = x, vis[x] = 1;
  for (register int i = last[x]; i; i = e[i].next) {
    int to = e[i].to;
    if (to == fa || vis[to]) continue;
 //   xoforsort[++tot] = to;
 		xNode[x].push_back(to);
  }
  std :: sort (xNode[x].begin(), xNode[x].end());
 // for (register int i = 1; i <= tot; i++) xNode[x].push_back (xoforsort[i]);
 // tot = 0;
  int k = xNode[x].size() - 1;
  for (register int i = 0; i <= k; i++) {
    work2 (xNode[x][i], x);
  }
}

inline void dfs (register int x, int fa) {
    if (vis[x]) return ;
  idx[++cnt] = x, vis[x] = 1;
  for (register int i = last[x]; i; i = e[i].next) {
    register int to = e[i].to;
    if (to == fa || vis[to]) continue ;
   // xoforsort[++tot] = to;
  	xNode[x].push_back(to);
  }
  std :: sort (xNode[x].begin(), xNode[x].end());
  //for (register int i = 1; i <= tot; i++) xNode[x].push_back (xoforsort[i]);
  //tot = 0;
  register int k = xNode[x].size () - 1;
  for (register int i = 0; i <= k; i++) {
    int to = xNode[x][i];
    if (vis[to]) {
      for (register int j = k; j > i; j--) 
        stack[++top] = xNode[x][j], f[stack[top]] = x;
      return;
    }
    if (cNode[to] && i == k) {
      if (stack[top] < to && top > 0) {
        return ;
      }
    }
    if (cNode[to]) {
      for (register int j = k; j > i; j--)
        stack[++top] = xNode[x][j], f[stack[top]] = x;
      dfs (to, x);
      flag = 1;
      if (x == root)
        while (top && cNode[f[stack[top]]]) top--, work2 (stack[top + 1], f[stack[top + 1]]);
      return ;
    } else work2 (to, x);
  }
}
inline void work (int x, int fa) {
    if (vis[x]) return;
  idx[++cnt] = x, vis[x] = 1;
  for (int i = last[x]; i; i = e[i].next) {
    int to = e[i].to;
    if (to == fa) continue;
   // xoforsort[++tot] = to;
   xNode[x].push_back(to);
  }
  std :: sort (xNode[x].begin(), xNode[x].end());
 // for (int i = 1; i <= tot; i++) xNode[x].push_back (xoforsort[i]);
 // tot = 0;
  for (int i = 0; i < xNode[x].size(); i++) {
    if (cNode[xNode[x][i]] && !flag) root = xNode[x][i], dfs (xNode[x][i], x);
    else work (xNode[x][i], x);
  }
}

int n, m;
int main () {
  //scanf ("%d%d", &n, &m);
  n = read(), m = read();
  for (int i = 1; i <= m; i++) {
    int x, y;
    x = read(), y = read();add (x, y), add (y, x);
  }
  cnt = 0;
  find_circle (1, 0);
  for (int i = 1; i <= n; i++) vis[i] = 0;
  if (m == n - 1) {
    work (1, 0);
    for (int i = 1; i <= n; i++) printf ("%d ", idx[i]);
    return 0;
  } else {
    //  for (int i = 1; i <= n; i++) if (cNode[i]) printf ("%d ", i);
    if (cNode[1]) root = 1, dfs (1, 0);
    else work (1, 0);
  }
  for (int i = 1; i <= n; i++) printf ("%d ", idx[i]);
  return 0;
}

评测结果