代码

#include<bits/stdc++.h>
//#define int long long
#define rep(i, l, r) for(register int i = l;i <= r; ++ i)
using namespace std;
inline int read()
{
	register char cc = getchar(); register int cn(0), flus(1);
	while(cc > '9' || cc < '0') {if(cc == '-') flus = -flus; cc = getchar();}
	while(cc >= '0' && cc <= '9') {cn = cn * 10 + cc - 48; cc = getchar();}
	return cn * flus;
}
const int N = 500010;
struct edge
{
	int to, next;
	bool del;
} e[N << 1];
int tot, head[N];
int n, m;
bool vis[N];
bool flag;
bool cir[N];
int point_in(1);
bool del = 0;
inline void add(int u, int v)
{
	e[++tot].next = head[u];
	head[u] = tot;
	e[tot].to = v;
	e[++tot].next = head[v];
	head[v] = tot;
	e[tot].to = u;
	return ;
}
//priority_queue<int> que;
void dfs(int u, int last)
{
	printf("%d ",u);
	priority_queue<int, deque<int>, greater<int> > que;
	for(register int i = head[u]; i; i = e[i].next)
	{
		int v = e[i].to;
		if(v == last || e[i].del) continue;
		//dfs(v, u);
		que.push(v);
	}
	while(!que.empty())
	{
		int v = que.top();
		que.pop();
		dfs(v, u);
	}
}
void dfs1(int u, int last)
{
	vis[u] = 1;
	for(register int i = head[u]; i; i = e[i].next)
	{
		int v = e[i].to;
		if(v == last || e[i].del) continue;
		if(vis[v])
		{
			flag = 1;
			cir[v] = 1;
			cir[u] = 1;
			return ;
		}
		dfs1(v, u);
		if(cir[v] && flag)
		{
			if(cir[u]) flag = 0;
			cir[u] = 1;
			return ;
		}
	}
}
void dfs2(int u, int last)
{
	// printf("dfs2 %d \n",u);
	vis[u] = 1;
	for(register int i = head[u]; i; i = e[i].next)
	{
		int v = e[i].to;
		// printf("v = %d \n",v);
		if(v == last) continue;
		if(cir[v])
		{
			point_in = v;
			return ;
		}
	}
}
int back(int u, int last)
{
	// printf("back %d %d \n",u,last);
	// priority_queue<int, deque<int>, greater<int> > q;
	int _min(1e9);
	int nxt;
	for(register int i = head[u]; i; i = e[i].next)
	{
		int v = e[i].to;
		// printf("v = %d \n",v);
		if(v == last) continue;
		if(!vis[v]) _min = min(_min, v);
		if(cir[v]) nxt = v;
	}
	// printf("_min = %d \n",_min);
	if(_min != 1e9)
	{
		return _min;
	}
	return back(nxt, u);
}
void dfs4(int u, int last)
{
	printf("");
//	printf("dfs4 %d %d \n",u,last);
	vis[u] = 1;
	priority_queue<int, deque<int>, greater<int> > q;
	for(register int i = head[u]; i; i = e[i].next)
	{
		int v = e[i].to;
		if(v == last) continue;
		q.push(v);
	}
	bool first(0);
	while(!q.empty())
	{
		if(del) return ;
		int v = q.top();
		q.pop();
		if(cir[v] && q.empty())
		{
			if(back(u, v) < v)
			{
				// printf("back(%d,%d) = %d \n",u,v,back(u, v));
				for(register int i = head[u]; i; i = e[i].next)
				{
					int v1 = e[i].to;
					if(v1 == v)
					{
						e[i].del = 1;
						if(e[i + 1].to == u) e[i + 1].del = 1;
						else if(e[i - 1].to == u) e[i - 1].del = 1;
					}
				}
				del = 1;
				return ;
			}
		}
		dfs4(v, u);
	}
	return ;
}
signed main()
{
	// printf("fuck \n");
//	freopen("in.txt","r",stdin);
	n = read(), m = read();
	rep(i, 1, m)
	{
		int u, v;
		u = read(), v = read();
		add(u, v);
	}
	if(n == m + 1)
	{
		dfs(1, 0);
		return 0;
	}
	dfs1(1, 0);
	memset(vis, 0, sizeof(vis));
	if(!cir[1]) dfs2(1, 0);
	// printf("point_in = %d \n",point_in);
	dfs4(point_in, 0);
	rep(i, 1, n)
	{
		// printf("cir[%d] = %d \n",i,cir[i]);
	}
	dfs(1, 0);
	return 0;
}

评测结果