3 ms·
Tarjan's strongly connected components algorithm[1] is designed to discover strongly connected components (interdependent vertices in graphs) but a side effect
by zamalek 13y ago
Tarjan's strongly connected components algorithm[1] is designed to discover strongly connected components (interdependent vertices in graphs) but a side effect is that it does a topological sort (I think I remember it being reversed). It runs in O(|V| + |E|) time (V = vertices, E = edges).
You might want to look into it.
[1]: http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_com...