越靠近叶子越优先删掉
- #include <iostream>
- #include <vector>
- #include <cstdio>
- using namespace std;
- int n, uu, hea[200005], cnt, deg[200005], fa[200005];
- bool vis[200005];
- vector<int> shu;
- vector<int> ans;
- struct Edge{
- int too, nxt;
- }edge[400005];
- void add_edge(int fro, int too){
- edge[++cnt].nxt = hea[fro];
- edge[cnt].too = too;
- hea[fro] = cnt;
- }
- void dfs(int x, int f){
- shu.push_back(x);
- fa[x] = f;
- for(int i=hea[x]; i; i=edge[i].nxt){
- int t=edge[i].too;
- if(t!=f) dfs(t, x);
- }
- }
- void shanchu(int x){
- vis[x] = true;
- ans.push_back(x);
- for(int i=hea[x]; i; i=edge[i].nxt){
- int t=edge[i].too;
- deg[t]--;
- if(t!=fa[x] && !vis[t]){
- if(deg[t]%2==0)
- shanchu(t);
- }
- }
- }
- int main(){
- cin>>n;
- for(int i=1; i<=n; i++){
- scanf("%d", &uu);
- if(!uu) continue;
- add_edge(uu, i);
- add_edge(i, uu);
- deg[i]++; deg[uu]++;
- }
- dfs(1, 0);
- for(int i=shu.size()-1; i>=0; i--){
- int x=shu[i];
- if(/*vis[x] ||*/deg[x]&1) continue;
- shanchu(x);
- }
- if(ans.size()!=n) printf("NO\n");
- else{
- printf("YES\n");
- for(auto i:ans) printf("%d\n", i);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2569655.html