Thursday, 18 August 2016

Even Tree

 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.

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 ui and vi 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
 
import java.util.*;
 public class Solution{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        Integer[][] edges = new Integer[M][2];
        for(int i=0;i<M;i++){
            edges[i][0] = in.nextInt();
            edges[i][1] = in.nextInt();
            if(edges[i][0]>edges[i][1]){
                int tmp = edges[i][0];
                edges[i][0] = edges[i][1];
                edges[i][1] = tmp;
            }
        }
        Arrays.sort(edges,new Comparator<Integer[]>(){
            @Override
            public int compare(Integer[] int1, Integer[] int2){
                Integer v1 = int1[0];
                Integer v2 = int2[0];
                return v1.compareTo(v2);
            }
        });
        int[] count = new int[N];
        count[0] = N;
        for(int i=1;i<N;i++){
            ArrayList<Integer> a = new ArrayList<Integer>();
            a.add(i+1);
            int j = 0;
            while(j<a.size()){
                for(int m=j;m<M;m++){
                    if(edges[m][0]==a.get(j)){
                        if(!a.contains(edges[m][1])){
                            a.add(edges[m][1]);
                        }
                    }
                }
                j++;
            }
            count[i] = a.size();
        }
        int remove = 0;
        for(int c:count){
            if(c%2==0)
                remove++;
        }
        System.out.println(remove-1);                  
    }
}
Post a Comment