代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN (500000+10)
#define INF 0x7fffffff

//本题的更优解法： 
//当在环上时，可拥有一次停止前进的机会，在机会可以使用的时候，判定使用这次机会会不会使结果更优，若会则停止前进 
//该解法可承受约500000的数据量，该级别的数据量无法利用邻接矩阵存储图的信息在转化，只能对边进行排序后再建图 
//排序的时间复杂度为O(nlogn)，找环和遍历的时间复杂度均为O(n)，因此总时间复杂度为O(nlogn)，空间复杂度为O(n) 
int n, m;
struct Node {int st, ed;}edge[MAXN*2];
bool cmp(struct Node a, struct Node b) {if(a.st!=b.st) return a.st>b.st; else return a.ed>b.ed;}
int head[MAXN*2], adj[MAXN*2], next[MAXN*2], tot=0;
int on_loop[MAXN], vis[MAXN], can_stop=1;//on_loop记录在节点是否在环上，can_stop记录停止前进的机会是否已经使用 
int ans[MAXN], node;

void Init(){
	memset(head, -1, sizeof(head));
	memset(adj, -1, sizeof(adj));
	memset(next, -1, sizeof(next));
}

void Addedge(int u, int v) {adj[++tot]=v, next[tot]=head[u], head[u]=tot;}

void Input(){
	Init();
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++)
		scanf("%d%d", &edge[i].st, &edge[i].ed), edge[i+m].st=edge[i].ed, edge[i+m].ed=edge[i].st;
	//因为使用的是前向星链表且要求输出字典序最小的遍历，所以需要进行排序并逆向插入链表 
	sort(edge+1, edge+1+m*2, cmp);
	for(int i=1; i<=m*2; i++)
		Addedge(edge[i].st, edge[i].ed);
}

bool Find_loop(int u, int fa){//寻找环 
	vis[u]=1;
	for(int tmp=head[u]; tmp!=-1; tmp=next[tmp])
		if(adj[tmp]!=fa){
			if(vis[adj[tmp]]==1) {on_loop[u]=on_loop[adj[tmp]]=1; return true;}
			//子节点已经访问过，表明已找到环，返回true表示已找到 
			else if(Find_loop(adj[tmp], u)==true && !on_loop[u]) {on_loop[u]=1; return true;}
			//返回过程中记录沿途各点 
			else if(on_loop[u])  return false;
			//越过最先经过的在环上的节点后，剩余节点已不再是环的范围，返回false 
		}
	return false;
}

void DFS(int u, int nxt){//minl记录如果现在停止继续前进，下一个将访问到的节点编号 
	ans[++node]=u, vis[u]=1;
	for(int tmp=head[u]; tmp!=-1; tmp=next[tmp])
		if(!vis[adj[tmp]]){
			//能停止继续前进的条件：当前处于环上，当前节点的所有子节点除位于环上的点以外已全部访问，还未使用停止前进的机会 
			if(on_loop[u]==1 && on_loop[adj[tmp]]==1 && can_stop){
				//如果满足停止前进的条件且停止前进会使序列更小，则选择停止前进 
				//注意停止前进后要把can_stop归零以防止多次停止前进 
				if(nxt<adj[tmp] && (next[tmp]==-1 || (vis[adj[next[tmp]]] && next[next[tmp]]==-1))) {can_stop=0; return;}
				//否则处理出下个在环上的节点停止前进时下一个将访问到的节点编号 
				for(int v=adj[tmp], tmp=head[u]; tmp!=-1; tmp=next[tmp])
					if(!vis[adj[tmp]] && adj[tmp]!=v) {nxt=adj[tmp]; break;}
			}
			DFS(adj[tmp], nxt);
		}
}

void Work(){
	memset(vis, 0, sizeof(vis));
	Find_loop(1, 0);
	memset(vis, 0, sizeof(vis));
	DFS(1, INF);
}

void Output(){
	for(int i=1; i<=n; i++)
		printf("%d ", ans[i]);
	printf("\n");
}

int main(){
	Input();
	Work();
	Output();
	return 0;
}

评测结果