### Problem

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 contains even number of vertices**
Your task is to calculate the number of removed edges in such a forest.

The first line of input contains two integers N and M. N is the number of vertices and M is the number of edges. 2 <= N <= 100.

Next M lines contains two integers u

Print a single integer which is the answer

**Input:**The first line of input contains two integers N and M. N is the number of vertices and M is the number of edges. 2 <= N <= 100.

Next M lines contains two integers u

_{i}and v_{i}which specifies an edge of the tree. (1-based index)**Output:**Print a single integer which is the answer

**Sample Input**

10 9

2 1

3 1

4 3

5 2

6 1

7 2

8 6

9 8

10 8

**Sample Output :**

2

**Explanation :**On removing the edges (1, 3) and (1, 6), we can get the desired result.

Original tree:

Decomposed tree:

Decomposed tree:

**Note:**The tree in the input will be such that it can always be decomposed into components containing even number of nodes.

**Analysis**

All Java Solutions on the InterviewStreet needs to run in 5 seconds with 256 MB maximum RAM available. So that means our solution can never be "Brute-Force" or O(n^2). Same applies to the space complexity.

**1 sec only**.

Create a map with parent as key and list of all its children. Now once this map is created, then take the root. Get each of its children from the list. So we have 1 as the node and 2, 3, 6 as children. So take 2. Check if the total number of nodes under it are even or odd (I am using a recursive call here to get the count.) In this case we have only two nodes - 7 and 5 (even number of nodes). So we cannot remove the link 1-3. Since that leaves with a subtree with 3-nodes (2, 7 and 5) which is not even number. So do not increment the count. However remove 2 from the list of 1's children and add 7 and 5 to the list.

Now take 6, it has 3 children (8, 9 and 10). So the link 1-6 can be removed. Increment counter, remove 6, add 8, 9 and 10 to the list.

The next entries 7, 5, and 4 have no children. Continue to 8. It has 2 children, hence cannot remove.

Now take the next element in the list - it is 3. It has only 1 child (odd number). So that means we can break 1-3 link. Increase the counter, remove 3 and add 4 to the list.

**Solution**

## No comments:

## Post a Comment