代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
using namespace std;

#define MAXN 5020
#define MAXM (4 * MAXN)
#define INF 0x3f3f3f3f
int n, m, delu, delv;
int hd[MAXN], dst[MAXM], nxt[MAXM], ec = 1;
vector<int> g[MAXN], ans, cur;
bool vis[MAXN];
pair<int, int> edges[MAXM];

void link(int u, int v) {
	nxt[++ec] = hd[u];
	hd[u] = ec;
	dst[ec] = v;
	g[u].push_back(v);
}

void dfs(int s, int fa) {
	ans.push_back(s);
	for (int i = 0; i < (int) g[s].size(); i++)
	if (g[s][i] != fa)
		dfs(g[s][i], s);
}

void tree() {
	dfs(1, 0);
	for (int i = 0; i < n; i++)
		cout << ans[i] << " ";
	cout << endl;
}

inline bool notdel(int u, int v) {
	return !((u == delu && v == delv) || (v == delu && u == delv));
}

void dfs_d(int u) {
//	cerr << u << endl;
	vis[u] = true;
	cur.push_back(u);
	for (int i = 0; i < (int) g[u].size(); i++)
	if (!vis[g[u][i]] && notdel(u, g[u][i])) dfs_d(g[u][i]);
}

void loop() {
	for (int i = 0; i < n; i++)
		ans.push_back(INF);
	for (int i = 0; i < m; i++) {
		cur.clear();
		memset(vis, false, sizeof(vis));
		delu = edges[i].first;
		delv = edges[i].second;
//		cerr << delu << " " << delv << endl;
		dfs_d(1);
		if ((int) cur.size() == n && cur < ans) ans = cur;
//		for (int i = 0; i < n; i++) cerr << cur[i] << " "; cerr << endl;
	}
	for (int i = 0; i < n; i++)
		cout << ans[i] << " ";
	cout << endl;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int p, q;
		cin >> p >> q;
		link(p, q);
		link(q, p);
		edges[i] = make_pair(p, q);
	}
	for (int i = 1; i <= n; i++) 
		sort(g[i].begin(), g[i].end());
	
//	cerr << "calc" << endl;
	if (n == m) {
		loop();
	} else {
		tree();
	}
	return 0;
}

评测结果