Kosaraju’s Algorithm

Kosaraju’s algorithm (Wikipedia) finds a graph’s strongly connected components in linear time.

The algorithm runs in two phases:

Phase 1:

  1. grab an unseen node and perform depth-first search.
  2. add node to stack after children processed.
  3. while unseen nodes exist…

Phase 2:

  1. pop node off stack.
  2. graph traversed against directed edges.
  3. all within traversal belong to one strongly-connected component.
  4. while stack is not empty…

This algorithm is used in my solving of SPOJ 13990. Web islands WEBISL; implementation is in git and below:

Leave a Reply