HackerRank Even Tree problem solution

In this 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.

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.)

HackerRank Even Tree problem solution in Python.

#!/usr/bin/python3
from collections import deque

tree_length, edges = map(int, input().strip().split())
tree = [list() for i in range(tree_length)]

for i in range(edges):
	parent, child = map(int, input().strip().split())
	parent -= 1
	child -= 1
	tree[parent].append(child)
	tree[child].append(parent)

def reconstruct(tree):
	visited = [False] * len(tree)
	queue = deque([0])
	reconstructed = [list() for i in range(len(tree))]
	while len(queue) > 0:
		current = queue.popleft()
		visited[current] = True
		for i in tree[current]:
			if not visited[i]:
				reconstructed[current].append(i)
				queue.append(i)
	return reconstructed

cuts = 0
def dfs(tree, index):
	global cuts
	subtrees = []
	for i in tree[index]:
		subtrees.append(dfs(tree, i))
	for vertices in subtrees[:]:
		if not vertices % 2:
			cuts += 1
			subtrees.remove(vertices)

	return sum(subtrees) + 1
tree = reconstruct(tree)
dfs(tree, 0)
print(cuts)

Even Tree problem solution in Java.

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);
    }
  }
}

Problem solution in C++.

#include <iostream>
#include <string.h>
#include <map>
#include <string>
#include <set>
#include <vector>
using namespace std;
int vis[110];
vector<int> vec[104];
vector<int> vec2[104];
int le[110];
int root[110];
void dfs(int t)
{
	vis[t]=1;
	bool tag=0;
	for(int i=0;i<vec[t].size();i++)
	{
		if(vis[vec[t][i]]==0)
		{
			root[vec[t][i]]=t;
			tag=1;
			vec2[t].push_back(vec[t][i]);
			dfs(vec[t][i]);
		}
	}
	if(tag==0)le[t]=1;
}
int mark[110],ret;
bool ischildallleaf(int i)
{
	for(int j=0;j<vec2[i].size();j++)
	{
		int t=vec2[i][j];
		if(mark[t]==0&&le[t]==0)return false;
	}
	return true;
}
int countt(int i)
{
	int cnt=0;
	for(int j=0;j<vec2[i].size();j++)
	{
		int t=vec2[i][j];
		if(mark[t]==0)cnt++;
	}
	return cnt;
}
void colo(int i)
{
	mark[i]=1;
	for(int j=0;j<vec2[i].size();j++)
	{
		int t=vec2[i][j];
		mark[t]=1;
	}
	return ;
}
int main()
{
	int n,m,i,j,p,q,ta,tb;
	cin>>n>>m;
	if(n-1!=m)while(1);
	memset(vis,0,sizeof(vis));
	for(i=1;i<=n;i++){vec[i].clear();vec2[i].clear();}
	for(i=1;i<n;i++)
	{
		cin>>p>>q;
		vec[p].push_back(q);
		vec[q].push_back(p);
	}
	memset(le,0,sizeof(le));
	root[1]=0;
	dfs(1);
	memset(mark,0,sizeof(mark));
	ret=0;
	int nn=n;
	while(nn>1)
	{
		for(i=1;i<=n;i++)
		{
			if(!mark[i]&&le[i]&&root[i]!=0&&ischildallleaf(root[i]))
			{
				int t=countt(root[i]);
				if(t%2==1)
				{
					ret++;
					colo(root[i]);
					if(root[i]!=0&&root[root[i]]!=0)
					{
						ta=0;
						tb=root[root[i]];
						for(j=0;j<vec2[tb].size();j++)
						{
							int r=vec2[tb][j];
							if(mark[r]==0)ta=1;
						}
						if(ta==0)le[tb]=1;
					}
					
				}
				else 
				{
					colo(root[i]);
					mark[root[i]]=0;
					le[root[i]]=1;
				}
				

				nn=0;
				for(j=1;j<=n;j++)if(mark[j]==0)nn++;
				break;
			}
		}
		//if(i==n+1)break;
	}
	cout<<--ret<<endl;
}

Problem solution in C.

#include<stdio.h>
#include<stdlib.h>
struct node 
{
	int vertex;
	struct node *down;
	struct node *right;
};
struct node *first;
int ret=0,count=0;
int dfs(int i,int n)
{
	int j,x;
	struct node *val,*hold;
	val=first;
	for(j=0;j<n;j++)
	{
		
		if(val->vertex==i)
		{
			
			count++;
			//printf("n Val of count is %d val of i is %dn",count,i);
			hold=val->right;
			while(hold!=NULL)
			{		
				x=hold->vertex;
				hold=hold->right;
				ret=dfs(x,n);
			}
			break;
		}
		else
			val=val->down;	
	}	
	return count;
}	
int main()
{
	int n,i,j,m,vi,vj,flag=1,p=0;
	struct node *loc,*val,*new,*ben,*hold;
	int *b;
		//printf("Enter the no of verticesn");
		scanf("%d %d",&n,&m);
		b=(int *)malloc(n*sizeof(int));
		loc=(struct node*)malloc(sizeof(struct node));
		loc->vertex=1;
		loc->down=NULL;
		loc->right=NULL;
		first=loc;
		val=loc;
		for(i=2;i<=n;i++)
		{
				
				loc=(struct node*)malloc(sizeof(struct node));
				loc->vertex=i;
				loc->right=NULL;
				val->down=loc;
				val=loc;
		}
		loc->down=NULL;
		//printf("Give the no of edges n");
		//scanf(" %d",&m);
		
		for(i=0;i<m;i++)
		{
					//printf("Give the edge source->destination Vi->Vj n");
					scanf("%d %d",&vi,&vj);
					loc=(struct node*)malloc(sizeof(struct node));
					loc->right=NULL;
					loc->down=NULL;
					loc->vertex=vi;
					val=first;
					for(j=1;j<=n;j++)
					{
						if(flag==1)
						{
							if(val->vertex==vj )
							{
								hold=val;
								if(hold->right==NULL)
									hold->right=loc;
								else
								{
									ben=hold->right;
									hold->right=loc;
									loc->right=ben;
								}	
								flag=0;		
							}
							else
								val=val->down;
						}
					}
					flag=1;
		}
		val=first;
		for(i=1;i<=n;i++)
		{
			hold=val;
			while(hold!=NULL)
			{	
				//printf("%d",hold->vertex);
				hold=hold->right;
			}
			//printf("n");
			val=val->down;
		}
		for(i=2;i<=n;i++)
		{		
				count=0;
				b[i]=dfs(i,n);
				//printf(" %d final %d n",b[i],i);
		}
		for(i=2;i<=n;i++)
		{
				if(b[i]%2==0)
					p++;
		}
		printf("%d",p);
	return 0;
}