Kosaraju's Algorithm

• used to find strongly connected components (components that can be reached)
• Time $O(V + E)$

Steps:

1. order the vertices in decreasing order of finish time in DFS (when recursion start -> start time; when all adj are processed -> finish time)

- create an empty stack
- for every vertex u,
    if u is not visited
        DFSRex(u, stack)
- while stack is not empty
    pop an item and add to result

DFSRec(u, stack):
    - mark u as visited
    - for every adjacent v
        if v is not visited
            DFSRec(v, stack)
    - add u to stack

2. Reverse all edges
3. Do DFS of the reversed graph in the order obtained in step 1. For every vertex, all reachable vertices are strongly connected.

note

It is not the best algorithm. Tarjan is more efficient