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
