Root of a graph can be any node whose in-degree is zero. i.e. there are no nodes pointing to that node. It can be found by using O( |V| ) space and O( |E| ) time . Now we can choose any node whose in-degree is zero if present. or choose any random node and itf DFS-tree is the desired tree. Time complexity of DFS is O(|E|).
On Monday, 12 March 2012 15:05:49 UTC+5:30, Umer Farooq wrote: > > Hello friends, > > I recently had an onsite MS interview. One of the questions that they > asked was: > > > - Given a directed graph, write a program that takes root of the graph > and returns root of a tree which comprises of all the nodes of the graph > in > the same way as they appeared in the graph (the graph contains no cycles). > > > -- > Umer > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/l-xn8uxltrwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
