HackerRank: Even Tree (V) C# solution - use queue to help counting spanning tree's node

April 23, 2016

  Problem statement:

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

C# solutions to study:

Code to study: 

 written by an engineer in Microsoft
https://gist.github.com/jianminchen/5c6b6cb4de9c4a2faf6237b7ac331a41

Julia modified the C# code to use DFS, spanning tree's node count, but still got the run time error/ wrong answer. 

https://gist.github.com/jianminchen/fe4da18247e4ad712c8e0bcb846983eb

Later, find out what is wrong. ( Probably, here is the reason:
The edge is directed. 
Do not duplicate the edge. 
For example, 2 1, just 2->1, do not add 1->2; 
but 
vertex[1].add(2), 
vertex[2].add(1), 
edge just add Tuple(2,1) )

Now, write exactly same code using study code, and see what I can learn.

The following code passes all the test cases.
https://gist.github.com/jianminchen/0e40bb76011e60f8aaf4683ed9c9c3d6

Julia's comment:

The edge is directed. Do not duplicate the edge and save two copy of the edge. But, vertex list is added for both vertexes of one edge.

Follow up - on April 24, 2016 8:40pm
Read Graph Toplogical Sorting:
http://www.geeksforgeeks.org/topological-sorting/

Follow up - on April 30, 2016 11:52pm
Read graph reprenstation
Use Adjacency Matrices
Use Adjacency Lists
https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs

Notes from the blog:
How much space do adjacency lists take? We have $|V|$ lists, and although each list could have as many as $|V|-1$ vertices, in total the adjacency lists for an undirected graph contain $2|E|$ elements. Why $2|E|$? Each edge $(i,j)$appears exactly twice in the adjacency lists, once in $i$'s list and once in $j$'s list, and there are $|E|$ edges. For a directed graph, the adjacency lists contain a total of $|E|$ elements, one element per directed edge.