「NOIP2018」旅行

朴素的做法就是删掉环上的一条边然后跑一次。

如果想在优化这个代码，就要尝试找到这条删去的边，把每一个点的儿子节点的编号排一个序。

对于环上的一个点，如果它想回溯，就必须要把儿子走完（当然不算下一个环上的点），所以如果下一个换上的点是儿子中最劣的，并且回溯比往下走更优，就可以确定删这条边了。

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

inline void read(int &x) {
	x = 0; int f = 0; char s = getchar();
	while (s < '0' || '9' < s) f |= s == '-', s = getchar();
	while ('0' <= s && s <= '9') x = x * 10 + s - 48, s = getchar();
	x = f ? -x : x;
}

const int N = 5e5 + 10;

int n, m;
struct node { int y, id; }; vector<node> e[N];
int siz, cir[N], bian[N], tp, sta[N], pre[N], ban;
bool huan[N], vis[N], v[N];

bool cmp(node p1, node p2) {
	return p1.y == p2.y ? p1.id < p2.id : p1.y < p2.y;
}

bool dfs1(int x) {
	sta[++tp] = x;
	vis[x] = 1;
	for (int i = 0; i < e[x].size(); i++) {
		int y = e[x][i].y, id = e[x][i].id;
		if (v[id]) continue;
		v[id] = 1;
		if (vis[y]) {
			for (int j = tp; j >= 1; j--)
				if (sta[j] == y) {
					for (int k = j; k < tp; k++) {
						huan[sta[k]] = 1;
						cir[++siz] = sta[k];
						bian[siz] = pre[sta[k + 1]];
					}
					huan[x] = 1;
					cir[++siz] = x;
					bian[siz] = id;
				}
			return 1;
		}
		pre[y] = id;
		if (dfs1(y)) continue;
	}
	tp--;
	vis[x] = 0;
	return 0;
}

void dfs2(int x) {
	vis[x] = 1;
	sta[++tp] = x;
	for (int i = 0; i < e[x].size(); i++) {
		int y = e[x][i].y, id = e[x][i].id;
		if (vis[y] || ban == id) continue;
		dfs2(y);
	}
}

int main() {
	freopen("travel.in", "r", stdin);
	freopen("travel.out", "w", stdout);
	read(n), read(m);
	for (int i = 1; i <= m; i++) {
		int x, y; read(x), read(y);
		e[x].push_back((node){y, i});
		e[y].push_back((node){x, i});
	}
	for (int i = 1; i <= n; i++)
		sort(e[i].begin(), e[i].end(), cmp);
	if (n == m) {
		dfs1(1);
		int sml = 1e9, x = cir[1], y;
		for (int j = e[x].size() - 1; j >= 0; j--) {
			if (e[x][j].y == cir[2]) break;
			if (e[x][j].id == pre[x]) continue;
			sml = min(sml, e[x][j].y);
		}
		for (int i = 2; i <= siz; i++) {
			if (i == siz) {
				ban = bian[i];
				break;
			} 
			x = cir[i], y = e[x][e[x].size() - 1].y;
			if (y == cir[i - 1]) y = e[x][e[x].size() - 2].y;
			if (y == cir[i + 1]) {
				if (y < sml) continue;
				ban = bian[i];
				break;
			}
			sml = 1e9;
			for (int j = e[x].size() - 1; j >= 0; j--) {
				if (e[x][j].y == cir[i + 1]) break;
				if (e[x][j].y == cir[i - 1]) continue;
				sml = min(sml, e[x][j].y);
			}
		}
	}
	tp = 0; memset(vis, 0, sizeof(vis)); dfs2(1);
	for (int i = 1; i <= tp; i++)
		printf("%d ", sta[i]);
	puts("");
	return 0;
}