# Hackerrank Even Tree 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  nodes can be cut at most  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  and , the number of nodes and edges.
The next  lines contain two integers  and  which specify nodes connected by an edge of the tree. The root of the tree is node .

Constraints.

Note: The tree in the input will be such that it can always be decomposed into components containing an even number of nodes.  is the set of positive even integers.

Output Format.

Print the number of removed edges.

2 1
3 1
4 3
5 2
6 1
7 2
8 6
9 8
10 8

Sample Output 1

2

Explanation 1

Remove edges  and  to get the desired result.

No more edges can be removed.

### Solution in java8

Approach 1.

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

public class Solution {

public static Map<Integer, ArrayList<Integer>> tree;
public static int count;

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

int numOfNodes = scanner.nextInt();
int numOfEdges = scanner.nextInt();

tree = new HashMap<Integer, ArrayList<Integer>>();
for (int i = 1; i <= numOfNodes; i++) {
tree.put(i, new ArrayList<Integer>());
}

for (int i = 0; i < numOfEdges; i++) {
int child = scanner.nextInt();
int parent = scanner.nextInt();

ArrayList<Integer> parentNode = tree.get(parent);
}

for (int i = 2; i <= tree.size(); i++) {
if ((countChildren(i) % 2) != 0) {
count++;
}
}

System.out.println(count);
}

public static int countChildren(int node) {
int totalChild = tree.get(node).size();
for (int child : tree.get(node)) {
totalChild += countChildren(child);
}
}

}

Approach 2.

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

public class Solution {
static int n;static boolean b[];static int ar[];
public static void main(String[] args) {
Scanner sc=new Scanner (System.in);
n=sc.nextInt();int e=sc.nextInt();
int a[][]=new int[n][n];
ar=new int[n];int c=0;
for(int i=0;i<e;i++)
{
int x=sc.nextInt()-1,y=sc.nextInt()-1;
a[x][y]++;
a[y][x]++;
}
b=new boolean[n];
b[0]=true;
child(a,0);
for(int i=1;i<n;i++)
if(ar[i]%2==0&&ar[i]!=0)
c++;

System.out.println(c);
}
public static int child(int a[][], int x)
{
int sum=0;
for(int j=0;j<n;j++)
{
if(a[x][j]!=0&&b[j]==false)
{
b[j]=true;
sum+=child(a,j)+1;
}
}
ar[x]=sum+1;
return sum;
}
}

Approach 3.

import java.io.BufferedReader;
import java.io.IOException;

class Node {
public int val;
public int root;
Node(int r) {
val = 1;
root = r;
}
}

public class EvenTree {
public static void main(String[] args) throws IOException{

int n = Integer.parseInt(inp[0]);
int m = Integer.parseInt(inp[1]);
Node[] nodeArr = new Node[n];

nodeArr[0] = new Node(-1);

for(int i = 1; i < n; i++) {
int u = Integer.parseInt(inp[0]);
int v = Integer.parseInt(inp[1]);
nodeArr[i] = new Node(v-1);
}
for(int i = n-1; i > 0; i--) {
nodeArr[nodeArr[i].root].val += nodeArr[i].val;
}
int count = 0;
for(int i = n-1; i > 0; i--) {
if(nodeArr[i].val % 2 == 0){
count++;
}
}
for(int i = 0; i < n; i++) {
//			System.out.println("i => " + i + ", val => " + nodeArr[i].val + ", root => " + nodeArr[i].root);
}
System.out.println(count);

}
}


### Solution in python3

Approach 1.

tn, te = map(int, input().rstrip().split())
ch = {}
tr = {}
for i in range(te):
tf, tt = map(int, input().rstrip().split())
if tt not in tr.keys(): tr[tt] = [tf]
else: tr[tt].append(tf)
ch[i] = 1

for i in range(te+1, 1, -1):
if i not in tr.keys():
ch[i] = 1
else:
for j in tr[i]:
ch[i] += ch[j]

c = 0
for i in range(te):
if ch[i] % 2 == 0:
c+=1

print(c)


Approach 2.

class Node:
def __init__(self):
self.parent = None
self.size = 1

# "self" contain child object reference.
#so i assign "parent" object as parent node of child.
self.parent = parent
# Increase size of all above parent.
while parent:
parent.size += 1
parent = parent.parent

if __name__ == '__main__':

t_nodes, t_edges = map(int, input().rstrip().split())

nodes = [Node() for _ in range(t_nodes+1)]

for i in range(t_edges):
t_from, t_to = map(int, input().rstrip().split())

res = sum(1 for node in nodes[1:] if node.size % 2 == 0 and node.parent is not None)

print(str(res) + '\n')


Approach 3.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the evenForest function below.
def evenForest(t_nodes, t_edges, t_from, t_to):
N = t_nodes
E = [[] for _ in range(N)]
for v1, v2 in zip(t_from, t_to):
E[v1-1].append(v2-1)
E[v2-1].append(v1-1)

score = [1] * N
singles = [i for i in range(N) if len(E[i]) == 1]
cuts = 0

while singles:
nd = singles.pop()
if not E[nd]:
continue
neighbour = E[nd][0]

if score[nd] % 2 == 0:
cuts += 1
else:
score[neighbour] += score[nd]

E[neighbour].pop(E[neighbour].index(nd))
if len(E[neighbour]) == 1:
singles.append(neighbour)

return cuts

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

t_nodes, t_edges = map(int, input().rstrip().split())

t_from = [0] * t_edges
t_to = [0] * t_edges

for i in range(t_edges):
t_from[i], t_to[i] = map(int, input().rstrip().split())

res = evenForest(t_nodes, t_edges, t_from, t_to)

fptr.write(str(res) + '\n')

fptr.close()


### Solution in cpp

Approach 1.

#include<cstdio>
using namespace std;
int n,m,i,j,x,y,k,copii[104],tata[104],v[104],a[104][104];
int nod(int k,int t)
{
for(int i=1;i<=a[k][0];i++)
if(a[k][i]!=t)
copii[k]+=1+nod(a[k][i],k);
tata[k]=t;
return copii[k];
}
int main()
{
//freopen("input","r",stdin);
//freopen("output","w",stdout);
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
a[x][0]++;
a[y][0]++;
a[x][a[x][0]]=y;
a[y][a[y][0]]=x;
}
copii[1]=nod(1,0);
for(i=1;i<=n;i++)
{
if(copii[i]%2==1&&tata[i]!=0)
{
tata[i]=0;
k++;
}
}
printf("%d",k);
return 0;
}


Approach 2.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int t;

void dfs(vector<vector<int> >& ver, vector<int>& first, vector<int> &last, int root)
{
first[root] = t;
++t;
for(int i = 0; i < ver[root].size(); ++i){
if(first[ver[root][i]] == -1)
dfs(ver, first, last, ver[root][i]);
}
last[root] = t;
}
int main() {
int v, e;
cin >> v >> e;
vector<vector<int> > ver(v);
int start, end;
for(int i = 0; i < e; ++i)
{
cin >> start >> end;
ver[start - 1].push_back(end - 1);
ver[end - 1].push_back(start - 1);
}
vector<int> first(v, -1);
vector<int> last(v, -1);
t = 0;
dfs(ver, first, last, 0);
int res = 0;
for(int i = 0; i < v; ++i)
if((last[i] - first[i])%2 == 0)
++res;
cout<<res-1<<endl;
}


Approach 3.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <ios>
#include <cstring>

using namespace std;

vector<int> graph[100];
bool visited[100];
int ans;

int dfs(int node) {
visited[node] = true;
int num_vertex = 0;

for(unsigned int i = 0; i < graph[node].size(); i++) {
int v = graph[node][i];
if(!visited[v]) {
int num_nodes = dfs(v);
if(num_nodes & 1)
num_vertex += num_nodes;
else
ans++;
}
}

return num_vertex + 1;
}

int main() {
ios_base::sync_with_stdio(false);

int m, n;

cin >> n >> m;

int u, v;
for(int i = 0; i < m; i++) {
cin >> u >> v;
graph[u - 1].push_back(v - 1);
graph[v - 1].push_back(u - 1);
}

ans = 0;
memset(visited, false, sizeof(bool) * 100);
dfs(0);

cout << ans << endl;

return 0;
}