You are given a tree (a simple connected graph with no cycles). You have to remove as many edges from the tree as possible to obtain a forest with the condition that : Each connected component of the forest should contain an even number of vertices.
To accomplish this, you will remove some edges from the tree. Find out the number of removed edges.
The first line of input contains two integers N and M. N is the number of vertices and M is the number of edges. The next M lines contain two integers ui and vi which specifies an edge of the tree. (1-based index)
Print the answer, a single integer.
\$2 \le N \le 100\$
10 9 2 1 3 1 4 3 5 2 6 1 7 2 8 6 9 8 10 8
Note: The tree in the input will be such that it can always be decomposed into components containing even number of nodes.
def parents(ar, child): """ Enumerates on the list of all the parents of a child.""" parent = ar[child] while child != parent: yield parent child = parent parent = ar[child] def update_child_count(node_parent, node_count, child): for parent in parents(node_parent, child): node_count[parent] += 1 if __name__ == '__main__': N, E = map(int, raw_input().split()) node_count = [None]*N node_parent = [None]*N root = 0 res = 0 for child, parent in enumerate(node_parent): node_parent[child] = child node_count[child] = 1 for node in xrange(E): child, parent = map(int, raw_input().split()) node_parent[child-1] = parent-1 update_child_count(node_parent, node_count, child-1) for child, parent in enumerate(node_count): if node_count[child] % 2 == 0 and child != root: res += 1 print res
The solution is working fine, but I am more interested in a better/more efficient approach.