Maximum number of edges removed so the each connected component of the forest should contain an even number of vertices.

Tomorrow is Thanksgiving day, to prepare myself for the holiday, I spent one hour to solve this graph problem found online. This is fun!

The problem source: https://www.hackerrank.com/challenges/even-tree

You are given a tree (a simple connected graph with no cycles). You have to remove as many edges from the tree as possible to obtain a forest with the condition that : Each connected component of the forest should contain an even number of vertices.

To accomplish this, you will remove some edges from the tree. Find out the maximum number of removed edges.

Approach: Greedy algorithm.

Iterate through all of the edges of the initial graph, then calculate the number of vertices of each subtree rooted at the two vertices of examined edge. If both numbers are even, then remove the edge. 

Here are the method and classes:

static List<EdgeG> edges = new ArrayList<EdgeG>();

public static class EdgeG{

NodeG one;
NodeG two;
public EdgeG(NodeG o, NodeG t){
this.one = o;
this.two = t;
}
}

public static int removeEdge(){

int counter = 0;

for(EdgeG e : edges){

if(e.one.size(e.two)%2==0 && e.two.size(e.one)%2==0){

//remove edge

counter++;

e.one.removeEdge(e.two);

e.two.removeEdge(e.one);

}

}

return counter;

}

To calculate the numbers of vertices for each subtree rooted at the two vertices of the examined edge, we can use Depth First Search. Here is the code

public static class NodeG{

int num;

List<NodeG> neighbors;

public NodeG(int n){
num = n;
neighbors = new ArrayList<NodeG>();
}

public int size(NodeG from){
NodeG n = this;
int counter = 0;
Set<NodeG> seen = new HashSet<NodeG>();
Stack<NodeG> s = new Stack<NodeG>();
s.add(n);
counter++;
while(!s.isEmpty()){
NodeG current = s.pop();
seen.add(current);
for(NodeG c : current.neighbors){
if(c!=from && !seen.contains(c)){
s.add(c);
counter++;
}
}
}
return counter;
}
}