cf#963B|cf#963B Destruction of a Tree(贪心 dfs序）
题目
【cf#963B|cf#963B Destruction of a Tree(贪心 dfs序）】http://codeforces.com/problemset/problem/963/B
题目大意
一棵树，每次消除度数为偶数的叶子节点以及他所有的边，问这个数能否被消除完（度数为0也是偶数哦）。能消除玩需要输出消除的顺序。
算法思路
将数dfs排序，每次先消除度数为偶数的dfs序大的节点。若先消除根节点，其叶子节点要是无法消除就没有办法了。
（贪心消除最靠近叶子的节点。因为如果最靠近叶子的偶数度节点晚于父节点消除，则父节点消除后此节点度数变为奇数，且其所有子节点度数都为奇数，就再也消除不了了。）
代码
#include
using namespace std;
const int maxn=2*1e5+10;
vectorvec[maxn];
vectorans;
stackst;
int pa[maxn];
int deg[maxn];
int vis[maxn];
void dfs(int u,int pre){
pa[u]=pre;
//记录其父亲节点
st.push(u);
//会按dfs序逆序弹出，这么做挺巧妙的…
for(int i=0;
i>n){
for(int i=0;
i<=n;
i++)
vec[i].clear();
ans.clear();
while(!st.empty())
st.pop();
memset(deg,0,sizeof(deg));
memset(vis,0,sizeof(vis));
for(int i=1;
i<=n;
i++){
int t;
cin>>t;
if(t){
vec[i].push_back(t);
vec[t].push_back(i);
deg[t]++;
deg[i]++;
}
}
dfs(1,-1);
while(!st.empty()){
int t=st.top();
st.pop();
if(deg[t]%2==0){
dfs2(t);
}
}
if(ans.size()==n){
cout<<"YES"<
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 怀念三里屯那家叫做the|怀念三里屯那家叫做the tree 的酒吧
- ztree|ztree 拖拽
- SourceTree|SourceTree 教程文档（了解界面）
- cs61b week8 -- Binary Search Tree
- webpack总结
- Codeforces|Codeforces Round #263 Div.1 B Appleman and Tree --树形DP【转】
- C++|C++ pbds 库平衡树（tree）
- 机器学习 — Decision Tree
- leetCode解题报告|leetCode解题报告之Binary Tree Level Order Traversal II,I(二叉树层次遍历)
- bootstrap|bootstrap treeview.js 权限加载时，复选框被选中的 demo