Kosaraju’s algorithm (

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

The algorithm runs in two phases:

**Phase 1:**

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

**Phase 2:**

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

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

*Related*