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.
Here's my Python code. I broke it down into three parts which made it a lot easier for me to think through. If testing my code, make sure to add "from queue import Queue"
Put the tree into a dictionary style format
Create a function to cut one edge from a single node of a tree and return the length of the resulting subtree
Run that function once per edge on the main tree and count the number of successes. The problem statement says the parent tree will always be an even length, and even - even = even, so it is not necessary to check both sides. And since there are no loops, it is not needed to record which edges have been cut.
defevenForest(t_nodes,t_edges,t_from,t_to):deffind_size(start,skip,graph):# Function to find the size of a subtree from graph from "start" excluding the edge connecting to "skip"l=1q=Queue()q.put(start)done={start,skip}whileTrue:curr=graph[q.get()]foriincurr:ifinotindone:q.put(i)done.add(i)l+=1ifq.empty():breakreturn(l)# Build the graph as a dictionary graph={}foriinrange(t_edges):ift_from[i]ingraph:graph[t_from[i]].append(t_to[i])else:graph[t_from[i]]=[t_to[i]]ift_to[i]ingraph:graph[t_to[i]].append(t_from[i])else:graph[t_to[i]]=[t_from[i]]# Cut each edge and check if the resulting subtree is even in lengthcuts=0foriinrange(t_edges):iffind_size(t_from[i],t_to[i],graph)%2==0:cuts+=1return(cuts)
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 →
Here's my Python code. I broke it down into three parts which made it a lot easier for me to think through. If testing my code, make sure to add "from queue import Queue"