Saturday, April 23, 2016

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: 

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


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.

No comments:

Post a Comment