HackerRank Even Tree Problem Solution

In this post, we will solve HackerRank Even Tree Problem Solution.

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 4 nodes can be cut at most 1 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 trodes and tedges, the number of nodes and edges.
The next tedges lines contain two integers tfrom[i] and to[i] which specify nodes connected by an edge of the tree. The root of the tree is node 1.

Even Tree C Solution

/* Enter your code here. Read input from STDIN. Print output to STDOUT */#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int e;
struct Node * next;
int no;

}node;



int cnt =0,visit[20],v=0;
node * arr;
void getcount(int start)
{
visit[start]=++v;
node * temp=arr[start].next;
while(temp)
{
if(!visit[temp->no])
getcount(temp->no);
temp=temp->next;
}

temp=arr[start].next;

while(temp)
{
if(arr[temp->no].e)
//printf("\n start:%d end:%d",start,temp->no),
cnt++;
else if(visit[start]<visit[temp->no])
{
//printf("\n setting 1:start:%d end:%d",start,temp->no);
arr[start].e^=1;
}temp=temp->next;
}


}
void init()
{
int nodes,edges;
scanf("%d%d",&nodes,&edges);

arr=malloc(sizeof(node)*(nodes+1));
int i;
for(i=1;i<=nodes;i++)
{
arr[i].next=NULL;arr[i].e=0;
arr[i].no=i;
visit[i]=0;
}
node * temp;

for(i=1; i<=edges;i++)
{
int start,end;
scanf("%d%d",&start,&end);
 temp=malloc(sizeof(node));
temp->next=arr[start].next;
temp->no=end;
arr[start].next=temp;

temp=malloc(sizeof(node));
temp->next=arr[end].next;
temp->no=start;
arr[end].next=temp;

}

}

int main()
{
init();
int i;


getcount(1);
printf("%d",cnt);
}

Even Tree C++ Soluton

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <list>
#include <utility>
using namespace std;

 
int main() {
 
 int child_counter(int,int,vector<list <int>>);
   int ans=0,v1,v2,s;
    int n,m;

    cin>>n>>m;
 vector<list <int> > adj(n+1);
    int visited[n+1]={0};
      list<int>que;
    for(int j=0;j<m;j++){
		cin>>v1>>v2;
        adj[v1].push_back(v2);
       adj[v2].push_back(v1);
	                    }
    que.push_back(1);
    visited[1]=1;
    list<int>::iterator i;
   while(!que.empty()){
 
        s=que.front();
 
        que.pop_front();
 
        for(i=adj[s].begin(); i!=adj[s].end() ; i++){
         
          
            if(visited[*i]==0){ que.push_back(*i); visited[*i]=1; if(child_counter(*i,s,adj)%2==0){ans++;} }
                                                 }
                        }
 
 
 
 
    cout<<ans;
 
    return 0;
}
   int child_counter(int s,int s1,vector<list<int>>adj){
int count=0;
    list<int>::iterator i;
  //  count+=adj[s].size();
   if(adj[s].size()>0){ for(i=adj[s].begin();i!=adj[s].end();i++){
       if((*i)!=s1){
           count+=child_counter(*i,s,adj);}
                                          }
                      }
 
return count+1;
}

Even Tree C Sharp Soluton

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace EvenTrees
{
    class Solution
    {
        static List<List<int>> trees;
        static Hashtable edges;
        
        static void CreateInitialTrees(int n)
        {
            trees = new List<List<int>>();
            for (int i = 0; i < n; i++)
            {
                List<int> temp = new List<int>();
                temp.Add(i + 1);
                trees.Add(temp);
            }
        }

        static bool IsAllEdgesDone()
        {
            bool returnValue = true;
            foreach (List<int> temp in edges.Values)
            {
                if (temp.Count != 0)
                {
                    returnValue = false;
                    break;
                }
            }
            return returnValue;
        }

        static void RemoveEdges(int x, int y)
        {
            List<int> tempList = edges[x] as List<int>;
            tempList.Remove(y);

            edges.Remove(x);
            edges.Add(x, tempList);
        }

        static int IsCardinalOne(List<int> list)
        {
            int cardinality = 0, returnValue = 0, originValue = 0;

            foreach (int num in list)
            {
                List<int> temp = edges[num] as List<int>;
                cardinality += temp.Count;
                if (cardinality > 1)
                {
                    return 0;
                }
                if (temp.Count == 1)
                {
                    returnValue = temp.ElementAt(0);
                    originValue = num;
                }
                
            }
            if (cardinality == 1)
            {
                RemoveEdges(originValue, returnValue);
                RemoveEdges(returnValue, originValue);
                return returnValue;
            }
            else
                return 0;            
        }

        static int ConnectedTo(List<int> list)
        {
            foreach (int temp in list)
            {
                if (((List<int>)edges[temp]).Count != 0)
                {
                    return ((List<int>)edges[temp]).ElementAt(0);
                }
            }
            return -1;
        }

        static void MergeLists(List<List<int>> toBeMerged)
        {
            if (toBeMerged.Count != 2)
            {
                //Console.WriteLine("Incorrect");
                return;
            }
            else
            {
                List<int> tempList = new List<int>();
                tempList.AddRange(toBeMerged.ElementAt(0));
                tempList.AddRange(toBeMerged.ElementAt(1));

                trees.Remove(toBeMerged.ElementAt(0));
                trees.Remove(toBeMerged.ElementAt(1));
                trees.Add(tempList);
            }
        }

        static List<int> FindList(int value)
        {
            foreach (List<int> temp in trees)
            {
                if (temp.Contains(value))
                    return temp;
            }
            return null;
        }

        static int ReduceEdges()
        {
            int removedEdges = 0, cardinalValue;
            
            do
            {
                List<List<int>> toBeMerged = new List<List<int>>();
                List<int> toBeMergedList = new List<int>();


                foreach (List<int> temp in trees)
                {
                    cardinalValue = IsCardinalOne(temp);
                    if (cardinalValue > 0)
                    {
                        if (temp.Count % 2 == 1)
                        {
                            toBeMergedList = FindList(cardinalValue);
                            toBeMerged.Add(temp);
                            toBeMerged.Add(toBeMergedList);
                            break;
                        }
                        else
                        {
                            removedEdges++;
                        }
                    }
                }

                MergeLists(toBeMerged);

            }
            while (!IsAllEdgesDone());

            return removedEdges;

        }

        static void Main(string[] args)
        {
            string line = Console.ReadLine();
            char[] delims = {' '};
            int x, y;
            List<int> temp;

            int n = Convert.ToInt32(line.Split(delims).ElementAt(0));
            int m = Convert.ToInt32(line.Split(delims).ElementAt(1));

            edges = new Hashtable();

            CreateInitialTrees(n);

            for (int i = 0; i < m; i++)
            {
                //Read an edge of the input tree.
                line = Console.ReadLine();
                x = Convert.ToInt32(line.Split(delims).ElementAt(0));
                y = Convert.ToInt32(line.Split(delims).ElementAt(1));
                     
                //Add with x as Key
                if (edges.ContainsKey(x))
                {
                    temp = edges[x] as List<int>;
                    edges.Remove(x);
                }
                else
                {
                    temp = new List<int>();
                }

                temp.Add(y);
                edges.Add(x, temp);

                //Add with y as key
                if (edges.ContainsKey(y))
                {
                    temp = edges[y] as List<int>;
                    edges.Remove(y);
                }
                else
                {
                    temp = new List<int>();
                }

                temp.Add(x);
                edges.Add(y, temp);
            }

            Console.WriteLine(ReduceEdges());
        }
    }
}

Even Tree Java Soluton

import java.io.*;
import java.util.*;

public class Solution {

  static class Node {
    int name;
    Node parent;
    List<Node> children;
    boolean odd=true;
  }
  
  Node[] buildTree(int numEdges, int[][] edgeData) {
    Node[] nodes = new Node[numEdges+1+1];
    for (int i=0; i<edgeData.length; i++) {
      int child = edgeData[i][0];
      int parent = edgeData[i][1];
      if (nodes[child] == null) {
        nodes[child] = new Node();
        nodes[child].name=child;
      }
      if (nodes[parent] == null) {
        nodes[parent] = new Node();
        nodes[parent].name=parent;
      }
      nodes[child].parent = nodes[parent];
      if (nodes[parent].children == null) {
        nodes[parent].children = new ArrayList<Node>();
      }
      nodes[parent].children.add(nodes[child]);
    }
    return nodes;
  }
  
  int dowork(int numEdges, int[][] edgeData) {
    Node[] nodes = buildTree(numEdges, edgeData);
    return makeEvenTrees(nodes[1]); // nodes[0] is not used, so that it's easy to keep track of node names..
  }

  int makeEvenTrees(Node node) {
    if (node == null) {
      return 0;
    }  
    int numCuts=0;
    if (node.children == null) {
      return 0; //no cut
    } else {    
      for (Node child : node.children) {
        numCuts += makeEvenTrees(child);
        if (child.odd) {
          node.odd ^= child.odd;
        } else {
          numCuts += 1;
        }
      }
    }
    return numCuts;
  }
  
  public static void main(String[] args) {
    Solution soln = new Solution();

    try (Scanner scan = new Scanner(System.in)) {
      int numNodes = scan.nextInt();
      int numEdges = scan.nextInt();
      int[][] edgeData = new int[numEdges][2];
      for (int i = 0; i < numEdges; i++) {
        edgeData[i][0] = scan.nextInt();
        edgeData[i][1] = scan.nextInt();
      }
      int result = soln.dowork(numEdges, edgeData);
      System.out.println(result);
    }
  }
}

Even Tree JavaScript Soluton

function processData(input) {
    input = input.split('\n');
    var topLine = input[0].split(' ');
    var N = topLine[0];
    var M = topLine[1];

    var cuts = 0;
    var queue = [];
    var checked = new Array(parseInt(N));
    var children = new Array(parseInt(N)+1);

    
    for(var i=0;i<=N;i++){
        children[i]=0;
    }
    
    queue.push(1);
    while(queue.length > 0){           

        var w = queue[queue.length-1];

        var count = 0;
        for(var i = 1; i<N; i++){
             var ln = input[i].split(' ');
              if(ln[1] == w && checked[ln[0]] !=1){
                   queue.push(ln[0]);
                   checked[ln[0]] = 1; 
                  count++;
              }
        }

        if(count == 0){
            
            var x = queue.pop();
            for(var i = 1; i<N; i++){
              var ln = input[i].split(' ');
              if(ln[0] == x){ 
                  children[parseInt(ln[1])] += children[parseInt(x)] + 1;
              }
            } 
        }
    }
       
    for(var i = 2; i< children.length;i++){
        children[i]++;
        
        if(children[i]!=0 && children[i]%2 == 0){
            cuts++;
        }
    }
    //console.log(children);
    console.log(cuts);

} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Even Tree Python Soluton

import sys

__author__ = 'bbyk'


def read_tree(N):
    tree = dict()
    while N:
        t, f = [int(i) for i in (cin.readline().split(' ', 1))]
        if f not in tree:
            tree[f] = [t]
        else:
            tree[f].append(t)
        N -= 1
    return tree


def num_to_remove(tree, node, cnt):
    if node not in tree:
        return 1
    sum = 1
    for i in tree[node]:
        ns = num_to_remove(tree, i, cnt)
        if not ns & 1:
            cnt[0] += 1
        else:
            sum += ns
    return sum


if __name__ == "__main__":
    cin = None

    if len(sys.argv) > 1:
        cin = open(sys.argv[1])
    else:
        cin = sys.stdin

    N, M = [int(i) for i in (cin.readline().split(' ', 1))]

    cnt = [0]
    num_to_remove(read_tree(M), 1, cnt)
    print(cnt[0])

    if cin is not sys.stdin:
        cin.close()
    pass

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python