One depth-first search finds every strongly connected component. Each node records its visit index and a low-link, the oldest node still on the stack that it can reach back to; a node whose low-link equals its own index is the root of a component, which is popped off the stack in one go.
- Average time
- O(V + E)
- Space
- O(V)