HackerRank: Even Tree - Graph Problem (I) - Just thinking

April 23, 2016

Problem statement:

https://www.hackerrank.com/challenges/even-tree

Motivation to work on graph problem:
1. There are over 10,000 submission on this problem, definitely, Julia likes to give it a try.

Statistics:
1:20 - 2:30pm  more than 1 hour wild thinking.

Think about the graph problem, before Julia writes any code, she think about how the problem is developed:

1. Have to remove as many edges from the tree as possible; <- kind of greedy algorithm
2. Each connected component of the forest should contain an even number of vertices.
<- Otherwise, odd number, 1 node itself, cannot be called forest; at least, 3.
3. Think about the how to remove one edge:
both ends should be ok; if one end only has one edge, then, no for removing the edge.
so, the node checks its edge count:
= 0 <- not possible - > "even number of vertices"
= 1 <- impossible
= 2 <- possible, can keep one, remove one

But think about forest with even number 2, 4,
for number 2, only one case:  3 connects to 4 in the test case
for number 4, only one case: one node in the center, all other 3 are connected to the same one.
for number 6, only one case: one node in the center, all other 5 are connected to the same one;
otherwise, one node connects to other 4 nodes, the 6th one will connect to the one of the node (other 4 nodes), then, it can be break into 2 and 4.

So, it should be two checking:
1. if the node only has one edge, keep it; do nothing;
2. if the node has more than one edge, remove all edges with more than 1 count.


Add comment on 10:00pm on April 23, 2016
1. Julia, you took distributed system in Florida Atlantic University around 2001, talking about spanning tree, ad hoc routing protocol; one thing is about spanning tree. Use DFS, and then, discuss spanning tree; if the root node's  child has a tree with even length, then, edge can be removed.