代码

#include <bits/stdc++.h>

#define R register
#define I inline

using namespace std;

const int N = 5e5 + 5;

int n, m;
int head[N], tot;
int ans[N], newans[N], dfn, flag, banu, banv;
int buf[20], num;
int cba;

vector <int> e[N];

I int read()
{
	int ret = 0; 
	char ch = getchar();
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch))
	{
		ret = (ret << 1) + (ret << 3) + (ch ^ 48);
		ch = getchar();
	}
	return ret;
}

I void write(int x)
{
    num = 0;
    while (x)
    {
        buf[ ++ num] = x % 10;
        x /= 10;
    }
    for (R int i = num; i; i -- )
        putchar(buf[i] + '0');
    putchar(' ');
}

void dfs(int u, int fa)
{
	if (dfn == n) return;
	newans[ ++ dfn] = u;
	if (newans[dfn] < ans[dfn]) cba = 1;
	else if (cba != 1 && newans[dfn] > ans[dfn])
	{
	    return;
	}
	for (R int i = 0; i < int(e[u].size()); i ++ )
	{
		int v = e[u][i];
		if (v == fa) continue;
		if (u == banu && v == banv) continue;
		if (v == banu && u == banv) continue;
		dfs(v, u);
	}
}

int main()
{
	n = read();
	m = read();
	int u, v;
	for (R int i = 1; i <= m; i ++ )
	{
		u = read();
		v = read();
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for (R int i = 1; i <= n; i ++ )
		sort(e[i].begin(), e[i].end());
	memset(ans, 0x3f, sizeof ans);
	if (m == n - 1) 
	{
		dfs(1, 0);
		for (R int i = 1; i <= n; i ++ )
			ans[i] = newans[i];
	}
	else
	{
		for (R int i = 1; i <= n; i ++ )
			for (R int j = 0; j < int(e[i].size()); j ++ )
			{
				dfn = flag = 0;
				banu = i;
				banv = e[i][j];
				cba = -1;
				dfs(1, 0);
				if (dfn < n) continue;
				for (R int k = 1; k <= n; k ++ )
					if (ans[k] > newans[k]) 
					{
						flag = 1;
						break;
					}
					else if (ans[k] < newans[k]) break; 
				if (flag)
					for (R int k = 1; k <= n; k ++ )
						ans[k] = newans[k];
			}
	} 
	for (R int i = 1; i <= n; i ++ ) write(ans[i]);
	return 0;
} 

评测结果