We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
A simple C++ solution using Depth First Search. The underlying principle is that you may cut an edge if and only if a subtree below that edge has an even number of nodes. We can calculate the number of nodes in a subtree for each node using recursion. If for any given node that number is even, we can cut the edge connecting the node to that subtree.
std::pair<int,int>DFS(intv,std::vector<std::set<int>>&g){intchildren=1,edges=0;for(intchild:g[v]){autop=DFS(child,g);edges+=p.second+!(p.first&1);children+=p.first;}return{children,edges};}// Complete the evenForest function below.intevenForest(intt_nodes,intt_edges,vector<int>t_from,vector<int>t_to){std::vector<std::set<int>>v(t_nodes);for(inti=0;i<t_edges;++i){v[t_to[i]-1].insert(t_from[i]-1);}returnDFS(0,v).second;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Even Tree
You are viewing a single comment's thread. Return to all comments →
A simple C++ solution using Depth First Search. The underlying principle is that you may cut an edge if and only if a subtree below that edge has an even number of nodes. We can calculate the number of nodes in a subtree for each node using recursion. If for any given node that number is even, we can cut the edge connecting the node to that subtree.