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.

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)

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