题意分析
$m=n-1$ 或 $m=n$，即这是一棵树或基环树。
显然，题意描述的小 Y 的路径会呈现为一棵树。
那么对于 $m=n-1$ 时的前 $60\%$ 的数据点，只需要 DFS 一遍记录序列即可，时间复杂度 $\mathcal O(n\log n)$，需要给边排序以保证字典序最小。
对于 $m=n$ 时，则会有一条边走不到，删去该边，剩余的部分构成一棵树。
则可以 $\mathcal O(n)$ 枚举删掉的边，然后 $\mathcal O(n)$ 判断。
注意删边后的图需要连通。
AC 代码
时间复杂度：$\mathcal O\left(n^2\right)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=5000,M=N;
int n,m;
pair<int,int>edge[M+1];
vector<int>g[N+1];
int del[N+1];
int ans[N+1],depth;
bool flag=false;
void dfs(int x,int fx){
ans[++depth]=x;
for(int &i:g[x]){
if(i==fx){
continue;
}
dfs(i,x);
}
}
bool vis[N+1];
int backup[N+1];
void dfs2(int x,int fx){
if(vis[x]){
flag=true;
return;
}
vis[x]=true;
depth++;
if(x>ans[depth]){
flag=true;
return;
}else if(x<ans[depth]){
ans[depth]=x;
for(int i=depth+1;i<=n;i++){
ans[i]=2147483647;
}
}
for(int &i:g[x]){
if(i==fx||i==del[x]){
continue;
}
dfs2(i,x);
if(flag){
return;
}
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
edge[i]={u,v};
}
for(int i=1;i<=n;i++){
sort(g[i].begin(),g[i].end());
}
if(m==n-1){
dfs(1,0);
}else{
fill(ans+1,ans+n+1,2147483647);
fill(backup+1,backup+n+1,2147483647);
for(int i=1;i<=m;i++){
del[edge[i].first]=edge[i].second;
del[edge[i].second]=edge[i].first;
memset(vis,0,sizeof(vis));
depth=0;
flag=false;
dfs2(1,0);
if(!flag){
bool check=true;
for(int i=1;i<=n;i++){
if(!vis[i]){
check=false;
}
}
if(!check){
for(int i=1;i<=n;i++){
ans[i]=backup[i];
}
}else{
for(int i=1;i<=n;i++){
backup[i]=ans[i];
}
}
}
del[edge[i].first]=0;
del[edge[i].second]=0;
}
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<' ';
}
cout<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
