寒鸽儿のBlog

$m = n-1$
贪心dfs,按照结点编号较小的输出即可。
$60pts$到手
$m = n$
这不就是一棵基环树嘛?

对于任意的方案,一种方案是走完整个环,另一种是走完n-1条边,然后回溯。回溯过程中我们还有选择的余地(可以访问其他子树),所以必然更优。
用dfs标记环上的每一个结点(类似强连通缩点),枚举断边即可。
$O(n^2)$

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define itra vector<int>::iterator

using namespace std;

const int N = 5678, INF = 0x3f3f3f3f;

vector<int> mp[N];
int n;

int sta[N], vis[N], bd[N], top, bp;
bool flg = true;
void find(int cur, int pre) {
	if(!flg) return;
	int sz = mp[cur].size();
	for(int i = 0; i < sz; ++i)
		if(mp[cur][i] != pre) {
			if(vis[mp[cur][i]]) {
				flg = false;
				--top;
				while(sta[top] != mp[cur][i])
					bd[bp++] = sta[top--];
				bd[bp++] = sta[top];
				bd[bp++] = cur;
				return;
			}
			vis[mp[cur][i]] = 1;
			sta[top++] = mp[cur][i];
			find(mp[cur][i], cur);
			if(!flg) return;
			--top;
		}
}

int ans[N], tat[N], ta, b1, b2;
void dfs(int cur, int pre) {
	tat[ta++] = cur;
	int sz = mp[cur].size();
	for(int i = 0; i < sz; ++i)
		if(mp[cur][i] != pre && !(cur==b1&&mp[cur][i]==b2) && !(cur==b2&&mp[cur][i]==b1)) {
			dfs(mp[cur][i], cur);
		}
}

inline bool ck() {
	for(int i = 0; i < n; ++i)
		if(ans[i] != tat[i])
			return tat[i] < ans[i];
	return false;
}

inline void upd() { if(ck()) for(int i = 0; i < n; ++i) ans[i] = tat[i]; }

int main() {
	memset(vis, 0, sizeof(vis));
	ans[0] = INF;
	int m, u, v;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d %d", &u, &v);
		mp[u].push_back(v); mp[v].push_back(u);
	}
	for(int i = 1; i <= n; ++i) sort(mp[i].begin(), mp[i].end());
	if(n == m) {
		top = bp = 0;
		vis[1] = 1;
		sta[top++] = 1;
		find(1, 0);
		for(int i = 0; i < bp - 1; ++i) {
			b1 = bd[i], b2 = bd[i+1];
			ta = 0;
			dfs(1, 0);
			upd();
		}
		for(int i = 0; i < n; ++i) printf("%d ", ans[i]);
		printf("\n");
	} else {
		dfs(1, 0);
		for(int i = 0; i < n; ++i) printf("%d ", tat[i]);
		printf("\n");
	}
	return 0;
}