1 You are given a tree (a graph with n vertices and n - 1 edges in which it's possible to reach any vertex from any other vertex using only its edges). 2 3 A vertex can be destroyed if this vertex has even degree. If you destroy a vertex, all edges connected to it are also deleted. 4 5 Destroy all vertices in the given tree or determine that it is impossible. 6 7 Input 8 The first line contains integer n (1 ≤ n ≤ 2·105) — number of vertices in a tree. 9 10 The second line contains n integers p1, p2, ..., pn (0 ≤ pi ≤ n). If pi ≠ 0 there is an edge between vertices i and pi. It is guaranteed that the given graph is a tree. 11 12 Output 13 If it's possible to destroy all vertices, print "YES" (without quotes), otherwise print "NO" (without quotes). 14 15 If it's possible to destroy all vertices, in the next n lines print the indices of the vertices in order you destroy them. If there are multiple correct answers, print any. 16 17 Examples 18 inputCopy 19 5 20 0 1 2 1 2 21 outputCopy 22 YES 23 1 24 2 25 3 26 5 27 4 28 inputCopy 29 4 30 0 1 2 3 31 outputCopy 32 NO
题目大意：有n个顶点，输入n个数字，记作p[i]，如果p[i]！=0，则表示有一条i到p[i]的边，要求你输出删除顶点的顺序，删除的条件有：1。这个点必须有偶数条边才能被删除 2。跟删除点连接的边都要去掉
分析：用一个in[maxn]的数组来记录连接u点的边数是偶数还是奇数，然后用dfs来跑遍所有的路，求出所有顶点是奇数还是偶数，最后递归打印即可
1 #define debug 2 #include<stdio.h> 3 #include<math.h> 4 #include<cmath> 5 #include<queue> 6 #include<stack> 7 #include<string> 8 #include<cstring> 9 #include<string.h> 10 #include<algorithm> 11 #include<iostream> 12 #include<vector> 13 #include<functional> 14 #include<iomanip> 15 #include<map> 16 #include<set> 17 #define pb push_back 18 #define dbg(x) cout<<#x<<" = "<<(x)<<endl; 19 using namespace std; 20 typedef long long ll; 21 typedef pair<int,int> pii; 22 typedef pair<ll,ll>PLL; 23 typedef pair<int,ll>Pil; 24 const ll INF = 0x3f3f3f3f; 25 const double inf=1e8+100; 26 const double eps=1e-8; 27 const int maxn =1e6; 28 const int N = 510; 29 const ll mod=1e9+7; 30 //------ 31 //define 32 bool ve[maxn]; 33 vector<int>G[maxn]; 34 int in[maxn]; 35 //dfs 36 void dfs(int u) { 37 for(int i=0; i<G[u].size(); i++) { 38 int tmp=G[u][i]; 39 if(tmp==u)continue; 40 dfs(tmp); 41 in[u]^=in[tmp]; 42 } 43 in[u]^=1; 44 } 45 void print(int u) { 46 for(int i=0; i<G[u].size(); i++) { 47 int tmp=G[u][i]; 48 if(tmp==u)continue; 49 if(!in[tmp]) { 50 print(tmp); 51 } 52 } 53 cout<<u<<endl; 54 for(int i=0; i<G[u].size(); i++) { 55 int tmp=G[u][i]; 56 if(tmp==u)continue; 57 if(in[tmp]) { 58 print(tmp); 59 } 60 } 61 } 62 //solve 63 void solve() { 64 int n,s; 65 cin>>n; 66 for(int i=0; i<n; i++) { 67 int u; 68 cin>>u; 69 if(u) { 70 G[u].push_back(i+1); 71 } else { 72 s=i+1; 73 } 74 } 75 dfs(s); 76 if(in[s]) { 77 cout<<"YES"<<endl; 78 print(s); 79 }else{ 80 cout<<"NO"<<endl; 81 } 82 } 83 //main 84 int main() { 85 ios_base::sync_with_stdio(false); 86 #ifdef debug 87 freopen("in.txt", "r", stdin); 88 // freopen("out.txt","w",stdout); 89 #endif 90 cin.tie(0); 91 cout.tie(0); 92 solve(); 93 /* 94 #ifdef debug 95 fclose(stdin); 96 fclose(stdout); 97 system("out.txt"); 98 #endif 99 */ 100 return 0; 101 }