HackerRank Even Tree Problem Solution

Yashwant Parihar,

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.

HackerRank Even Tree Problem Solution
HackerRank Even Tree Problem Solution

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

Leave a Reply

Your email address will not be published. Required fields are marked *