Kosaraju's algorithm
/ koh-suh-RAH-zhoo /
Kosaraju's algorithm finds all the strongly connected components of a directed graph — the clusters of mutually reachable vertices — using nothing fancier than two ordinary depth-first searches. Its charm is conceptual clarity: it leans on one elegant observation about reversing all the arrows, and from that the components fall out almost by magic. If you can run DFS, you can run Kosaraju.
It works in three steps. First, run DFS over the whole graph and record the order in which vertices finish, pushing each onto a stack as it finishes. Second, build the reverse graph by flipping the direction of every edge. Third, repeatedly pop vertices off the stack (so you process them in decreasing finish time) and, for each one not yet assigned, run a DFS in the reverse graph; every vertex that single reverse-DFS reaches forms exactly one strongly connected component. Why does this work? The key fact is that reversing all edges leaves the SCCs unchanged (a round trip in the original is still a round trip when every arrow flips), but it cuts the one-way bridges between SCCs in the opposite direction. Processing vertices in decreasing finish order means you always start a reverse-DFS in the SCC that sits 'latest' in the condensation DAG; because the cross-component edges in the reverse graph all point the wrong way to escape, that reverse-DFS is trapped inside one SCC and floods exactly it. Peeling SCCs off in this order keeps each flood confined to a single component.
Kosaraju runs in O(n + m) — two linear DFS passes plus building the reverse graph — and it is a favourite for teaching because each piece is a plain traversal you already understand, with the cleverness concentrated in the finish-order-on-the-reverse-graph idea. The practical caveat versus Tarjan's algorithm: Kosaraju makes two passes over the graph and needs to construct the reversed edge set, so it touches the data twice and uses extra space for the reverse copy, whereas Tarjan computes the SCCs in a single DFS. Same big-O, but if you only get one pass over a huge graph or cannot afford to store the reverse, Tarjan is the leaner choice.
Graph a->b, b->c, c->a, c->d. First DFS from a might finish d, then c, b, a — stack top is a. Reverse the edges (b->a, c->b, a->c, d->c). Pop a, reverse-DFS reaches a,c,b but not d (the reversed edge is d->c, not c->d): SCC {a,b,c}. Pop d: SCC {d}.
Reversing arrows preserves each SCC but blocks escape; decreasing finish order keeps each reverse-DFS trapped in one component.
Kosaraju's correctness hinges on processing vertices in DECREASING finish time from the first pass and running the second DFS on the REVERSED graph — swap either and it breaks. It is O(n+m) but makes two passes; Tarjan does it in one.