Tweak tarjan implementation
Tweak tarjan implementation

Summary:
This diff makes a few fairly straight-forward changes to the implementation of
Tarjan's stongly-connect component algorithm. The new version more closely
reflects the "textbook" implementation.

Instead of storing indices, lowlinks, and stack membership in separate hash
tables, we can create our own node records with mutable fields. Since we already
have the node at hand, we can avoid a bunch of lookups.

Further, instead of the "not_yet_visited" logic, we can just iterate over the
roots. Note that the previous choose+remove operation is needlessly expensive,
because choose is actually logN (alias for min_element), and iteratively
removing every element of a set causes unnecessary rebalancing.

It is true that visiting one root might recursively visit another root, but we
can protect against that easily by checking if the index has been set.

Reviewed By: avikchaudhuri

Differential Revision: D16750100

fbshipit-source-id: 37c6fdac1e211b6c26beaaa358f5de84b1039d59

nmote/flow,nmote/flow,nmote/flow,nmote/flow,nmote/flow,nmote/flow,nmote/flow