[Verse 1] Graph theory heavyweight, strongly connected scenes Kosaraju's breaking down what connectivity means First pass runs a simple DFS on every node Finishing time stamps are the secret we decode Stack them up in order, highest finish wins the race Transpose that graph structure, flip each edge in place Second pass starts fresh, pop the stack and dive again Each component found reveals the strongly connected zen [Chorus] Two DFS sweeps, that's the magic recipe First pass orders nodes, second finds community Transpose the edges, stack the finishing times Kosaraju cracks the code in polynomial rhymes SCC detection, linear time precision Two-pass algorithm, perfect graph division [Verse 2] Start with any vertex, explore until you're stuck Mark the finishing moment, that's where algorithms luck Build a stack of completions, deepest searches first Then reverse every arrow, quench that knowledge thirst Pop the highest finisher from your ordered collection DFS again but backwards, find each strong connection Every tree discovered in this second exploration Maps exactly to one strongly connected constellation [Chorus] Two DFS sweeps, that's the magic recipe First pass orders nodes, second finds community Transpose the edges, stack the finishing times Kosaraju cracks the code in polynomial rhymes SCC detection, linear time precision Two-pass algorithm, perfect graph division [Bridge] Forward graph establishes the hierarchy Transpose reveals the true connectivity Finishing times become the guiding light Two linear passes solve the problem right [Verse 3] Why does transposition make the magic work so clean? Forward edges break between components in between But reverse them and the structure shifts dramatically Only strong components stay connected naturally Mathematics proves this elegant design Order plus reversal draws the perfect line Kosaraju knew the secret hiding in plain sight Two simple DFS calls illuminate the night [Outro] Stack the finish times, flip the graph around Strongly connected components will be found Linear complexity, elegant and tight Kosaraju's theorem burning algorithm bright
← Tarjan's algorithm (strongly connected components) | Prim's algorithm →