Tarjan's Algorithm

Tarjan's algorithm finds every strongly connected component in a directed graph with a single DFS pass. It does not need to reverse the graph or run a second traversal, which is what Kosaraju's algorithm requires.

The same core idea also gives us bridges, articulation points, and 2-edge-connected components. These show up in network reliability problems, compiler optimization (finding loops in control flow graphs), and graph interview questions.

This chapter walks through how Tarjan's algorithm works, traces it step by step on a sample graph, and then extends the core idea to find bridges and articulation points.