题目链接：https://www.luogu.org/problem/P5022
这道题目一开始看的时候没有思路，但是看到数据范围里面有一个：
\(m = n-1\) 或 \(m = n\) ，一下子有了思路。
当 \(m = n-1\) 时，这就是一棵树，以1为根节点进行搜索，每次优先访问编号小的点即可。
当 \(m = n\) 时，可知只有一个环，找到环中对应的所有边，然后遍历每一条环中的边，假设删除它，然后就变成了一棵树。
时间复杂度为：\(O(n^2)\) 。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5050;
struct Node {
int u, v, id;
Node() {}
Node(int _u, int _v, int _id) { u = _u; v = _v; id = _id; }
} edge[maxn*2], loop_edge[maxn];
vector<Node> g[maxn];
int n, m, p[maxn], pe[maxn], cnt, depth[maxn];
bool vis[maxn], vise[maxn*2], marked[maxn*2];
int ans_seq[maxn], tmp_seq[maxn], ans_cnt, tmp_cnt;
bool cmp(Node a, Node b) {
return a.v < b.v;
}
void find_loop(int u, int pre, int d) {
vis[u] = true;
depth[u] = d;
int sz = g[u].size();
for (int i = 0; i < sz; i ++) {
int v = g[u][i].v, id = g[u][i].id;
if (v == pre) continue;
if (!vis[v]) {
vise[id] = vise[id^1] = true;
p[v] = u;
pe[v] = id;
find_loop(v, u, d+1);
}
}
}
void select_loop_edges(int u, int v, int id) {
loop_edge[cnt++] = Node(u, v, id);
while (u != v) {
if (depth[u] > depth[v]) {
loop_edge[cnt++] = Node(p[u], u, pe[u]);
u = p[u];
}
else if (depth[u] < depth[v]) {
loop_edge[cnt++] = Node(p[v], v, pe[v]);
v = p[v];
}
else {
loop_edge[cnt++] = Node(p[u], u, pe[u]);
u = p[u];
loop_edge[cnt++] = Node(p[v], v, pe[v]);
v = p[v];
}
}
}
void dfs(int u, int pre) {
tmp_seq[tmp_cnt++] = u;
int sz = g[u].size();
for (int i = 0; i < sz; i ++) {
int v = g[u][i].v, id = g[u][i].id;
if (v == pre || marked[id] || marked[id^1]) continue;
dfs(v, u);
}
}
void final_check() {
bool flag = false;
if (ans_seq[0]) {
for (int i = 0; i < n; i ++) {
if (ans_seq[i] > tmp_seq[i]) { flag = true; break; }
else if (ans_seq[i] < tmp_seq[i]) break;
}
}
else
flag = true;
if (flag) for (int i = 0; i < n; i ++) ans_seq[i] = tmp_seq[i];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i ++) {
int u, v, w;
scanf("%d%d", &u, &v);
g[u].push_back(Node(u, v, i*2));
g[v].push_back(Node(v, u, i*2+1));
edge[i*2] = Node(u, v, i*2);
edge[i*2+1] = Node(v, u, i*2+1);
}
for (int i = 1; i <= n; i ++) sort(g[i].begin(), g[i].end(), cmp);
if (m == n) {
find_loop(1, -1, 1);
for (int i = 0; i < 2*m; i += 2) {
if (!vise[i]) {
int u = edge[i].u, v = edge[i].v;
select_loop_edges(u, v, i);
break;
}
}
for (int i = 0; i < cnt; i ++) {
marked[loop_edge[i].id] = marked[loop_edge[i].id^1] = true;
tmp_cnt = 0;
dfs(1, -1);
final_check();
marked[loop_edge[i].id] = marked[loop_edge[i].id^1] = false;
}
}
else { // m == n-1
dfs(1, -1);
final_check();
}
for (int i = 0; i < n; i ++) {
if (i) putchar(' ');
printf("%d", ans_seq[i]);
}
puts("");
return 0;
}