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