题意分析
旅行原题中是 $\mathcal O\left(n^2\right)$ 的，但是加强版中 $n\leq500000$，因此需要优化。
对于 $m=n-1$ 的情况，可以直接 DFS 一遍求得答案。
但是对于 $m=n$ 的情况，原题是 $\mathcal O(m)$ 枚举断边，因此效率低下。
考虑如何快速确定环上的边应不应该断。
令断边为 $(u,v)$。
则 $f_u,u,v$ 均在环上，否则会不连通；其中 $f_u$ 表示节点 $u$ 的父节点。
还需满足：
-
$v$ 为 $u$ 最大的子节点，否则字典序一定更劣。
-
$v>\textit{}nxt$，其中 $\textit{nxt}$ 表示从点 $u$ 向上回溯后，访问的第一个新节点。
否则字典序一定更劣。
搞清楚这三个条件后，题目便很简单了。
对于实现，可以将 $f_x$ 在 $x$ 的邻接表里删除，便于寻找最大子节点。
可以将 $\textit{nxt}$ 作为 DFS 的参数传递。
AC 代码
时间复杂度：$\mathcal O(n\log n)$。
其瓶颈其实在于给边排序，可以使用基数排序做到 $\mathcal O(n)$。
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
//#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=500000,M=N;
int n,m;
vector<int>g[N+1];
int ans[N+1],size;
bool flag=false;
void dfs(int x,int fx){
ans[++size]=x;
for(int &i:g[x]){
if(i==fx){
continue;
}
dfs(i,x);
}
}
vector<int>ring;
bool inRing[N+1];
bool findRing(int x,int fx){
static int flag[N+1];
static vector<int>s;
if(flag[x]){
for(int i=s.size()-1;i>=flag[x];i--){
ring.push_back(s[i]);
inRing[s[i]]=true;
}
return true;
}
flag[x]=s.size();
s.push_back(x);
for(int i:g[x]){
if(i==fx){
continue;
}
if(findRing(i,x)){
return true;
}
}
flag[x]=0;
s.pop_back();
return false;
}
bool returned;
bool vis[N+1];
void dfs2(int x,int fx,int nxt){
// cerr<<"dfs2("<<x<<","<<fx<<","<<nxt<<")\n";
//删除父节点,便于处理
if(fx){
g[x].erase(lower_bound(g[x].begin(),g[x].end(),fx));
}
ans[++size]=x;
vis[x]=true;
//可能需要回溯(不走环上点)
if(!returned && inRing[fx] && inRing[x] && inRing[g[x].back()] && g[x].back() > nxt){
returned=true;
for(int i=0;i<g[x].size()-1;i++){
if(/*g[x][i]==fx||*/vis[g[x][i]]){
continue;
}
if(i+1<g[x].size()-1){
dfs2(g[x][i],x,g[x][i+1]);
}else{
dfs2(g[x][i],x,nxt);
}
}
}else{
for(int i=0;i<g[x].size();i++){
if(/*g[x][i]==fx||*/vis[g[x][i]]){
continue;
}
if(i+1<g[x].size()){
dfs2(g[x][i],x,g[x][i+1]);
}else{
dfs2(g[x][i],x,nxt);
}
}
}
}
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);
}
for(int i=1;i<=n;i++){
sort(g[i].begin(),g[i].end());
}
if(m==n-1){
dfs(1,0);
}else{
findRing(1,0);
dfs2(1,0,N+1);
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<' ';
}
cout<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
/*
10 10
10 7
9 4
10 4
10 3
6 10
9 8
3 8
5 8
2 6
10 1
1 10 3 4 9 8 5 6 2 7
*/
