悬赏 May_Cry_ 的关注。

评测记录

#include<bits/stdc++.h>
using namespace std;
const int QAQ=5e5+7;
int n,m,huan[QAQ];
vector<int> dian[QAQ];
int rd[QAQ],ans[QAQ],cnt,zui[QAQ],shang=2e9;
void add(int u,int v)
{
	rd[u]++,rd[v]++;
	dian[u].push_back(v);
	dian[v].push_back(u);
}
queue<int> dui;
bool vis[QAQ],hui;
void dfs(int x)
{
	vis[x]=1;
	ans[++cnt]=x;
	int no=0;
	if(huan[x])
	{
		if(!hui)
		{
			if(!vis[zui[x]]&&huan[zui[x]]&&shang<zui[x])
			{
				hui=1;
				no=1;
			}
		}
		int sg=0;
		for(int v:dian[x])
		{
			if(vis[v]) continue;
			if(huan[sg])
			{
				shang=v;
				break;
			}
			sg=v;
		}
		for(int v:dian[x])
		{
			if(vis[v]) continue;
			if(no&&huan[v]) continue;
			dfs(v);
		}
	}
	else
	{
		for(int v:dian[x])
			if(!vis[v])
				dfs(v);
	}
}

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;i++) if(rd[i]==1) dui.push(i);
	while(!dui.empty())
	{
		int x=dui.front();dui.pop();
		for(int v:dian[x])
		{
			rd[x]--;
			rd[v]--;
			if(rd[v]==1) dui.push(v);
		}
	}
	for(int i=1;i<=n;i++) if(rd[i]==2) huan[i]=1;
	for(int i=1;i<=n;i++) sort(dian[i].begin(),dian[i].end()),zui[i]=dian[i][(int)dian[i].size()-1];
	dfs(1);
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	return 0;
}