[NOIP2018 提高组] 旅行

题目大意

给定一棵树或基环树，从起点出发，找到一个字典序最小的遍历序列。

题解

可以用 STL set 来存储边，这样字典序排序比较好做。如此，树的部分就直接遍历一遍即可。

考虑基环树的情况，先找到环，然后枚举删除环的每一条边，总复杂度是 $\mathcal{O}(n^2)$ 的。

代码

const int N = 5e4 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	set <pair<int, int> > e[N];
	int ans[N], tmp[N];
	bool Better() {
		for (int i = 1; i <= n; i++) 
			if (ans[i] != tmp[i]) return ans[i] > tmp[i];
		return 0;
	}
	
	int curId = -1, delId = -1;
	int vis[N];
	void dfs (int u) {
		vis[u] = curId;
		tmp[++tmp[0]] = u;
		if (tmp[0] == n && Better()) memcpy (ans, tmp, sizeof tmp);
		for (auto i = e[u].begin(); i != e[u].end(); ++i) {
			int v = i->first, id = i->second;
			if (vis[v] == curId || id == delId) continue;
			dfs(v);
		}
	}
	
	int cir[N], rho, flag;
	void Circle(int u, int fa) {
		vis[u] = curId;
		for (auto i = e[u].begin(); i != e[u].end(); ++i) {
			int v = i->first, id = i->second;
			if (v == fa || id == cir[1]) continue;
			if (vis[v] == curId) {
				rho = v;
				flag = 1;
				cir[++cir[0]] = id;
				break;
			}
			Circle (v, u);
			if (flag) cir[++cir[0]] = id;
			if (u == rho) flag = 0;
		}
	}
	
	int main () {
		n = Read(), m = Read();
		ans[1] = 1 << 30;
		for (int i = 1; i <= m; i++) {
			int u = Read(), v = Read();
			e[u].insert(make_pair(v, i));
			e[v].insert(make_pair(u, i));
		}
		if (n == m) {
			Circle(1, -1);
			for (int i = 1; i <= cir[0]; i++) {
				delId = cir[i], curId = i, tmp[0] = 0;
				dfs(1);
			}
		} else {
			dfs(1);
		}
		for (int i = 1; i <= n; i++) printf ("%d ", ans[i]);
		putchar(10);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}