Buttercola: Zenefits: Validate a Directed Graph Tree

Buttercola: Zenefits: Validate a Directed Graph Tree

Understand the problem:If the graph is undirected graph, it would be the same as the Leetcode question : Graph Valid Tree. 
http://buttercola.blogspot.com/2015/08/leetcode-graph-valid-tree.html

The corner case which need to be very careful is if the graph contains more than one connected components, i.e. multiple islands. In this case, the graph is not a valid tree because a tree can have one and only one root. 

The same role applies to the directed graph. For a directed graph, we can do a topological sorting. If a valid topological sorting exists, it means the graph does not contain a circle. 
But how to deal with multiple connected components? 

One solution is to calculate the in-degree for each node. For a valid tree, there should be one and only one node with in-degree 0. If not, e.g. there are two nodes with in-degree 0, the graph must not be a valid tree. Then we can also do a topological sort from this root node, avoiding starting from each and every node. 

Read full article from Buttercola: Zenefits: Validate a Directed Graph Tree