The simplest approach is probably to compute the transitive closure of the graph. Then look at each pair (row k, column k) of the closure. When they're equal, k is an element of bottom. All this requires O(n^3). Since n <= 5000, this should take a few seconds in the worst case.
On Oct 13, 12:52 pm, praba karan <[email protected]> wrote: > spoj.pl/problems/BOTTOM > > my algo for this prob goes by this way..will this work correctly? > > 1)first make a bfs from an arbitrary node and store the nodes visited > in order in an array. > > 2)the node that is visited at the end of the BFS in the 1st bfs is now > taken as the root and then make a BFS from this node and store the > nodes visited in order in an array. > > 3)reverse the array in step 2 > > 4)find the Longest Common Subsequence between the arrays in step 1 and > step 3 > > 5)if any one of the array is empty,then all the other nodes in the > other array sud b printed. > > will this logic work? > > any other ideas are welcomed... > > praba... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
