@@ -0,0 +1,2426 @@
+package algorithms.graph_theory;%0D%0A%0D%0Aimport java.util.Arrays;%0D%0Aimport java.util.Scanner;%0D%0A%0D%0A/*%0D%0A * Problem Statement: %0D%0A * You are given a tree (a simple connected graph with no cycles). You have to%0D%0A * remove as many edges from the tree as possible to obtain a forest with the%0D%0A * condition that : Each connected component of the forest should contain an%0D%0A * even number of vertices.%0D%0A * %0D%0A * To accomplish this, you will remove some edges from the tree. Find out the%0D%0A * number of removed edges.%0D%0A * %0D%0A * Input Format:%0D%0A * The first line of input contains two integers N and M. N is the number of%0D%0A * vertices and M is the number of edges.%0D%0A * The next M lines contain two integers ui and vi which specifies an edge of%0D%0A * the tree. (1-based index)%0D%0A * %0D%0A * Output Format:%0D%0A * Print the answer, a single integer.%0D%0A * %0D%0A * Constraints:%0D%0A * 2 %3C= N %3C= 100.%0D%0A * %0D%0A * Note: The tree in the input will be such that it can always be decomposed%0D%0A * into components containing even number of nodes.%0D%0A * %0D%0A * Sample Input: %0D%0A * 10 9%0D%0A * 2 1%0D%0A * 3 1%0D%0A * 4 3%0D%0A * 5 2%0D%0A * 6 1%0D%0A * 7 2%0D%0A * 8 6%0D%0A * 9 8%0D%0A * 10 8%0D%0A * %0D%0A * Sample Output: %0D%0A * 2%0D%0A */%0D%0Apublic class EvenTree %7B%0D%0A%0D%0A    public static void main(String%5B%5D args) %7B%0D%0A        %0D%0A        int tree%5B%5D;%0D%0A        int count%5B%5D;%0D%0A               %0D%0A        Scanner sc = new Scanner(System.in);%0D%0A               %0D%0A        int numVertices = sc.nextInt();%0D%0A        int numEdges = sc.nextInt();%0D%0A               %0D%0A        tree = new int%5BnumVertices%5D;%0D%0A        count = new int%5BnumVertices%5D;%0D%0A        Arrays.fill(count, 1);%0D%0A               %0D%0A        for (int i = 0; i %3C numEdges; i++) %7B%0D%0A                        %0D%0A            int childVert = sc.nextInt();%0D%0A            int parentVert = sc.nextInt();%0D%0A                   %0D%0A            tree%5BchildVert - 1%5D = parentVert;%0D%0A                   %0D%0A            count%5BparentVert - 1%5D += count%5BchildVert - 1%5D;%0D%0A                   %0D%0A            int root = tree%5BparentVert - 1%5D;%0D%0A                   %0D%0A            while(root != 0) %7B%0D%0A                count%5Broot - 1%5D += count%5BchildVert - 1%5D;%0D%0A                root = tree%5Broot - 1%5D;%0D%0A            %7D%0D%0A        %7D%0D%0A        sc.close();%0D%0A               %0D%0A        int counter = -1;%0D%0A                %0D%0A        for(int i = 0; i %3C numEdges; i++) %7B%0D%0A                        %0D%0A            if(count%5Bi%5D %25 2 == 0) %7B%0D%0A                counter++;%0D%0A            %7D%0D%0A                   %0D%0A        %7D%0D%0A        System.out.println(counter);%0D%0A    %7D%0D%0A%7D

Add EvenTree