发现大部分题解都是O(n^2)的复杂度，这里分享一个O(n)复杂度的方法。
首先前60%的情况，图是一棵无根树，只要从1开始DFS，每次贪心走点的编号最小的点就行了。（为什么？因为当走到一个点u时，若不把以它为根的子树的所有点都遍历一遍的话，回溯到u的父亲后，就再也没可能遍历u的没有遍历过的儿子了。）
再看剩下40%的情况，由于题目保证图是一个无向连通图，当 边数 等于 点数减一 时图必为树，在此基础上再多加一条边，就在一棵树的基础上形成一个环（为了方便，后文仍会提到树，而后文的树指的是图没有第n条边时形成的树）。有了环会发生什么？发现有了环后第一种情况的贪心+DFS解法的依据就不成立了，即走到一个点u时，即使不把以它为根的子树的所有点都遍历一遍，当回溯到u的父亲后，也有可能会通过环的一部分到达u节点剩下的没有遍历过的儿子。显然不能再无脑贪心了。
仔细思考一下两种情况的不同，发现若一棵子树中没有环，也没有点能直接连向环，那这棵子树就可以用第一种情况的贪心+DFS的方法处理。若一个点u及它的儿子v都在环上，那么若要u走到v，既可以直接走u到v的连边(u,v)，也可以从u开始反方向绕环一圈走到v；若u和v至少有一个点不在环上，那么从u到v只能通过边(u,v)，即只有一个到达方法。这就说明，若一对父子都在环上，那他们之间有两种到达方法；否则就只有一种到达方法。
这时两种情况的不同就明确了：同样的是：对于一个与环没有什么关系的子树（没有关系指不与环的任何一个边相交。若与环共用最多一个点，也没事。），用贪心+DFS做就好，因为当父亲回溯后未被遍历的儿子就不能再被遍历到了；不同的是，第二种情况多了父子都在环上的情况，这时父亲回溯一次后，儿子仍能被遍历。但因为“小 Y 的旅行方案是这样的：任意选定一个城市作为起点，然后从起点开始，每次可 以选择一条与当前城市相连的道路，走向一个没有去过的城市，或者沿着第一次访问该 城市时经过的道路后退到上一个城市。”，所以每个父亲最多也只能回溯一次。
所以我们只要搞清楚第一次环上的回溯何时发生就行了，只要发生了一次环上的回溯，第二种情况就可以当第一种情况做了（一旦环上的某个点u回溯了，那么它的儿子与它的连边就不会再用了，也相当于没有这条边，此时图只有n-1条边，就是棵树）。“环上的回溯”显然只会发生在环上（毕竟名字都说是“环上的”了）,这其实就相当于在第一次环上的回溯发生前，环上的点可以“主动”发起回溯，即就算它的儿子还没有都被遍历完，它也可以回溯，不过那个没有被遍历的儿子只能是环上的点。
思考为什么要主动回溯。我们各种乱搞，不就是为了最后的字典序最小吗？而为了达成这个目标，我们只要保证能遍历到所有点的同时，时刻最小化当前的字典序，即每次都遍历可行的编号最小的点。于是我们可以记录一下主动回溯后可以得到的最小字典序就行啦。先跑一边tarjan找到环。从第一次进入环开始就记录主动回溯后可以得到的最小字典序（sec变量），若当前点u在环上，且只剩一个同在环上的儿子了，并且儿子的编号还大于sec，那就主动回溯；不然就正常dfs就行。
具体实现看代码吧：
#include<iostream>
#include<cstdio>
#include<queue> #define min(a,b) ((a)>(b)?(b):(a)) using namespace std; const int N=; int n,m,x,vis[N],lst[N],xu[N],cntxu,nxt[N<<],to[N<<],cnt;
int dfn[N],dfss,low[N],huan[N],sta[N],top; char ch; inline int read()
{
x=;
ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
} void tarjan(int u,int fa)
{
dfn[u]=low[u]=++dfss;
sta[++top]=u;
int Top=top;
vis[u]=;
int t;
for(int e=lst[u];e;e=nxt[e])
{
if(!dfn[t=to[e]])
{
tarjan(t,u);
low[u]=min(low[t],low[u]);
}
else
{
if(t!=fa&&vis[t])
low[u]=min(low[t],low[u]);
}
}
if(dfn[u]==low[u])
{
if(Top==top)
vis[sta[top--]]=;
for(int i=Top;i<=top;++i)
{
huan[sta[i]]=;//是环
vis[sta[i]]=;
}
top=Top-;
}
} int fir;//有没有进过环
int sec=-;//-1标记意义为还没有进入过环 void dfs(int u)
{
if(vis[u]) return;
priority_queue<int,vector<int>,greater<int> >hep;//用堆维护当前要dfs的最小值。由于每个节点的儿子都很少，所以时间复杂度为几乎可以忽略的常数
xu[++cntxu]=u;//记录答案序列
vis[u]=;
for(int e=lst[u];e;e=nxt[e])
if(!vis[to[e]])
hep.push(to[e]);
int head;
if(huan[u]&&!fir)
{
fir=;
while(!hep.empty())
{
head=hep.top();
hep.pop();
if(!huan[head]) dfs(head);//不在环上的点正常贪心DFS。
else
{
if(!vis[head]&&sec==-)
{
sec=hep.top();
dfs(head);
}
else//第一次环上回溯发生后，都正常贪心DFS
dfs(head);
}
}
}
else
{
if(!huan[u]||(huan[u]&&sec==-))
{
while(!hep.empty())
{
if(!vis[hep.top()])
dfs(hep.top());
hep.pop();
}
}
else
{
while(!hep.empty())
{
head=hep.top();
hep.pop();
if(!huan[head])
dfs(head);
else
{
if(head<=sec)
{
if(!hep.empty())
sec=hep.top();
dfs(head);
}
else
{
if(hep.empty())
{
sec=-;//主动回溯，并把sec设成-2标记第一次环上的回溯已经结束了
return;
}
else//在环上的点，要没有 不在环上的儿子 时才能考虑主动回溯
{
sec=hep.top();
dfs(head);
while(!hep.empty())
{
dfs(hep.top());
hep.pop();
}
} }
}
}
}
}
} inline void addedge(int u,int v)
{
nxt[++cnt]=lst[u];
lst[u]=cnt;
to[cnt]=v;
} int main()
{
n=read(),m=read();
int u,v;
for(int i=;i<=m;++i)
{
u=read(),v=read();
addedge(u,v);
addedge(v,u);
}
tarjan(,);
dfs();
for(int i=;i<=n;++i)
printf("%d ",xu[i]);
return ;
}