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
I didnt understand the above solution, but I have a bad complexity
solution.
Make an nXn boolean adjacency matrix.
Run transitivy closure on the matrix.
For every node w, check if for all v E V, w->v=> v->w
On Oct 13, 9:52 pm, praba karan wrote:
> spoj.pl/problems/BOTTOM
>
> my algo for this prob
