1) Find all strongly connected components in the graph.
(http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm)
2) Reducing each strongly connected component to a single
vertex,preserving all inter-component edges.
The resulting graph is a directed acyclic graph (DAG)
3) Find all vertexes with no out edge in the DAG, then all vertexes of
the corresponding strongly connected components forms the bottom of graph.
All 3 steps can be computed in O(n+m) time complexity.
On 2010-10-14 0:52, praba karan 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 algoge...@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.
