题解 P5049 【旅行（数据加强版）】

~~我们选择n方过百万~~ 树的情况很容易解决，一直往编号小的子节点DFS下去就行了。 ``m=n`` 也就是带有一个环。~~这里我们考虑拆边解决~~。 冷静分析一波，我们发现：初始状态下，从一个点走向环上的一个点存在**至多**两种方法。换言之，我们在不断取最小儿子向下走时可以放弃当前子树回溯**一次**。 显然，上述放弃子树反悔祖先是有一定条件的。例如，下图所示情况不能返回祖先，否则当前点的子树将永远无法到达。  再如下图，当前点的子树是环（或子树中有环）也不能立即回溯。  这样也不行呢qwq  看来只有这样子才可以暂时放弃子树回溯了：（也就是当前点和当前点的子结点都在环上，当前点的父亲也在环上）  当然，满足可回溯条件时我们并不会马上无脑回溯，而会先考虑回溯能否使解变得更优。这个其实很简单，看看未遍历的祖先(及其儿子)中最小的一个是否小于当前点的决策，这条信息在DFS时传递下去即可。 放弃子树的回溯**只能用一次**qwq ```cpp #include <cstdio> #include <cstring> #include <algorithm> #define maxn 500005 #define maxe (maxn << 1) using namespace std; int n, m, stck[maxn], top, cir = 1, in[maxn], cnt; int ans[maxn], to[maxn << 2], s[maxn], idx = 0, len = 0; int lnk[maxn], nxt[maxe], son[maxe], tot = 1; bool vis[maxn], flg[maxn]; int num = 0; inline int read() { char ch = getchar(); int ret = 0, f = 1; while (ch > '9' || ch < '0') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = getchar(); return ret * f; } void adde(int x, int y) { son[++tot] = y, nxt[tot] = lnk[x], lnk[x] = tot; } void Trump() { memset(flg, 1, sizeof(flg)); for (int i = 1; i <= n; ++i) flg[i] = true; top = 0; for (int i = 1; i <= n; ++i) { if (in[i] == 1) stck[++top] = i; } while (top) { int now = stck[top--]; flg[now] = 0, cnt--; for (int j = lnk[now]; j; j = nxt[j]) { in[son[j]]--; if (in[son[j]] == 1) stck[++top] = son[j]; } } } void DFS(int now, int lst, int pre) { if (!vis[now]) { ans[++idx] = now; if (flg[now]) cnt--; } vis[now] = 1; int l = len + 1, r = len; for (int j = lnk[now]; j; j = nxt[j]) { if (!vis[son[j]]) to[++len] = son[j]; } if (len < l) return; r = len, len++; sort(to + l, to + 1 + r); if (s[now] == 0) s[now] = 1; for (s[now] = l; s[now] <= r; ++s[now]) { if (s[now] == r) { if (flg[to[s[now]]] && flg[now] && flg[pre] && to[s[now]] > lst && cir < 0) { cir = 1; return; } DFS(to[s[now]], lst, now); } else DFS(to[s[now]], to[s[now] + 1], now); } } int main() { freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); n = read(), m = read(); memset(s, 0, sizeof(s)); for (int i = 1; i <= m; ++i) { int x = read(), y = read(); adde(x, y), adde(y, x); in[x]++, in[y]++; } if (n == m) { cir = -1, cnt = n; Trump(); flg[0] = true; } DFS(1, n + 1, 0); for (int i = 1; i <= n; ++i) printf("%d ", ans[i]); return 0; } ``` NOIp的时候脑残，用环上挂着的链来判回溯条件，炸掉3个点QAQ