首先达成一个共识,n为偶数,无法做到 因为n为偶数,最后奇数条边,和每次撕偶数条边不符合
n为奇数时,做dfs 首先一个除了root每个点都是奇数度的树,可以通过先序序列把这个树撕掉(这个自己脑补) 如果上述成立,那么我可以直接dfs,从离叶子最近的地方找这种树,并且把他撕掉 大概就像从叶子不断向上撕差不多 就可以了 核心就是找 除了root每个点都是奇数度的最小子树
#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <vector> using namespace std; typedef long long ll; const int N = 2e5 + 5; #define MS(x, y) memset(x, y, sizeof(x)) #define MP(x, y) make_pair(x, y) const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 9; vector<int> E[N]; int sz[N]; int degree[N]; int Stack[N]; int tot; int Id[N]; void dfs(int x, int pre) { sz[x] = 1; Stack[++tot] = x; Id[x] = tot; if (pre != x) degree[x] ^= 1; int evenp = 1; for (int i = 0; i < E[x].size(); ++i) { int to = E[x][i]; if (to == pre) continue; dfs(to, x); sz[x] += sz[to]; if (sz[to]) { degree[x] ^= 1; evenp &= (sz[to] & 1); } } if (evenp && (degree[x] == 0)) { sz[x] = 0; for (int i = Id[x]; i <= tot; ++i) { printf("%d\n", Stack[i]); } tot = Id[x] - 1; } } int main() { int n; while (~scanf("%d", &n)) { tot = 0; memset(degree, 0, sizeof(degree)); for (int i = 1; i <= n; ++i) E[i].clear(); int rt; for (int i = 1; i <= n; ++i) { int a; scanf("%d", &a); if (a) { E[i].push_back(a); E[a].push_back(i); } } if (n % 2 == 0) { printf("NO\n"); } else { printf("YES\n"); dfs(1, 1); } } return 0; } /* 5 0 1 2 1 2 5 5 0 1 2 3 3 */转载于:https://www.cnblogs.com/Basasuya/p/8878766.html
相关资源:垃圾分类数据集及代码