Even Tree - Hackerrank Problem Solution in Python

Even Tree

Hackerrank Problem Solution

Even Tree - Hackerrank Problem Solution

PROBLEM STATEMENT

You are given a tree (a simple connected graph with no cycles).

Find the maximum number of edges you can remove from the tree to get a forest such that each connected component of the forest contains an even number of nodes.

As an example, the following tree with  nodes can be cut at most  time to create an even forest.

Function Description

Complete the evenForest function in the editor below. It should return an integer as described.

evenForest has the following parameter(s):

• t_nodes: the number of nodes in the tree
• t_edges: the number of undirected edges in the tree
• t_from: start nodes for each edge
• t_to: end nodes for each edge, (Match by index to t_from.)

Input Format

The first line of input contains two integers  and , the number of nodes and edges.
The next  lines contain two integers  and  which specify nodes connected by an edge of the tree. The root of the tree is node .

Constraints

Note: The tree in the input will be such that it can always be decomposed into components containing an even number of nodes.  is the set of positive even integers.

Output Format

Print the number of removed edges.

---

SOLUTION IN PYTHON

#!/bin/python3 import math import os import random import re import sys def evenForest(t_nodes, t_edges, t_from, t_to): weight={} for i in range(t_edges-1,-1,-1): if t_from[i] in weight: weight[t_from[i]]+=1 else: weight[t_from[i]]=1 if t_to[i] in weight: weight[t_to[i]]+=weight[t_from[i]] else: weight[t_to[i]]=weight[t_from[i]] return(len([1 for key in weight if weight[key]%2==0])) if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') t_nodes, t_edges = map(int, input().rstrip().split()) t_from = [0] * t_edges t_to = [0] * t_edges for i in range(t_edges): t_from[i], t_to[i] = map(int, input().rstrip().split()) res = evenForest(t_nodes, t_edges, t_from, t_to) fptr.write(str(res) + '\n') fptr.close()

Share Share Tweet Share Share Share

LIKE?

SHARE If you find this useful, please share with your friends and Community.
CODE TOGETHER..GROW TOGETHER.