[Verse 1] Graph connections running deep and wide Strongly connected components we must find Kosaraju knew the secret to the game Two DFS passes bring components to their name Start with any vertex take your pick Depth first search until the stack gets thick Fill it up with finish times in order Then transpose the graph and cross the border [Chorus] First pass forward stack them high Second pass backward components fly Transpose the edges flip the flow Kosaraju's method this is how we go DFS twice and you will see Connected groups in harmony Stack and flip the magic trick Kosaraju's algorithm does it quick [Verse 2] Forward pass explores each unvisited node Push to stack when backtracking down the road Finishing times determine the sequence Later finishers get stack precedence Now we flip every single edge around Transpose graph with connections turned around What pointed left now points to right Setting up for our second flight [Chorus] First pass forward stack them high Second pass backward components fly Transpose the edges flip the flow Kosaraju's method this is how we go DFS twice and you will see Connected groups in harmony Stack and flip the magic trick Kosaraju's algorithm does it quick [Verse 3] Pop the stack in reverse finish order Start DFS from each node like a reporter In transposed graph each tree we find Represents one component combined All vertices reached in single traversal Form a group that's universal Mutually reachable every way That's strongly connected we can say [Bridge] Linear time complexity we achieve Two passes through is all we need O of V plus E running clean Most efficient algorithm you've seen When cycles exist in directed graphs Kosaraju finds the connected paths [Chorus] First pass forward stack them high Second pass backward components fly Transpose the edges flip the flow Kosaraju's method this is how we go DFS twice and you will see Connected groups in harmony Stack and flip the magic trick Kosaraju's algorithm does it quick [Outro] Two DFS one transpose stack Strongly connected that's a fact Kosaraju showed us the way Components found in linear day
← Tarjan's algorithm (strongly connected components) | Prim's algorithm →