Exercise: Practice the Kosaraju-Sharir Algorithm

The task at hand

Grab a pen and a piece of paper, and figure out how to use the two-pass Kosaraju-Sharir algorithm to find the SSCs of the following digraph. Assume that the depth-first search implementation picks vertices with smaller indices first.

Verify the solution in three steps by clicking the “Run FirstPassDFS of G” button.

Note:

• You may also try experimenting on a different digraph that can be created following these instructions.instructions
• If the automatically generated labels overlap with vertices or edges, you may view them more clearly by dragging the vertices of the given digraph (after selecting the “Drag vertices” checkbox).