Ordering tasks: what a topological sort is
Picture a directed graph whose edges mean "must come before." Courses with prerequisites, build steps that depend on earlier outputs, chapters that reference earlier chapters — draw an edge u to v whenever u has to happen before v. A topological order is a single line-up of all the vertices such that every edge points forward: for each edge u to v, u appears somewhere to the left of v. Lay the vertices out left to right in that order and no arrow ever points backward. If such a line-up exists, you can do the tasks one at a time, in that order, and never violate a dependency. This is the topological ordering of a directed acyclic graph, and it is one of the cleanest things graph exploration gives us.
Two honest caveats up front. First, a topological order exists if and only if the graph has no directed cycle. A cycle a to b to a is a dependency that says a before b and b before a at the same time — no line-up can satisfy both, so there is nothing to sort. That is exactly why the input must be a DAG (directed acyclic graph). Second, the order is usually not unique: if two tasks have no path between them, either may come first, so a graph can have many valid topological orders. The algorithm produces one of them, not "the" canonical one.
Finish times do the work
Here is the surprise the previous guide set up. When depth-first search explores a vertex, it stamps two times: a discovery time when it first arrives, and a finish time when it has fully explored everything reachable below and is about to back out. The claim is almost magical: in a DAG, if you sort the vertices by decreasing finish time, you get a valid topological order. Equivalently, just push each vertex onto a stack the moment it finishes; popping the stack hands you the vertices in topological order. No extra pass, no sorting by a separate key — the finish order, reversed, is already the answer.
Why is that true? Take any edge u to v and watch what depth-first search must do with it. We need to show u finishes after v, so that u lands to the left of v in the reversed-finish order. There are exactly two cases at the moment the edge u to v is examined. If v is still undiscovered, DFS dives into v from u and finishes v before it returns to finish u — so v finishes first, good. If v is already finished, then it finished before we are even done examining u, so again u finishes later, good. The only remaining possibility — v discovered but not yet finished — would mean v is an ancestor still on the recursion stack, making u to v a back edge and revealing a cycle. In a DAG there are no back edges, so that case never happens. Every edge therefore goes from a later-finishing vertex to an earlier-finishing one, which is exactly forward-pointing in the reversed order.
Why a topological order is worth having
A topological order is not just a tidy list; it is a license to process vertices in an order where every dependency is already done. The cleanest payoff is shortest paths on a DAG. On a general graph, single-source shortest paths needs Dijkstra or Bellman-Ford, but if the graph is acyclic you can do something simpler and faster: lay the vertices in topological order and relax each one's outgoing edges in that order. Because every predecessor of a vertex comes before it, by the time you reach a vertex its best distance is already final. This works in plain O(V + E) time and, unlike Dijkstra, it handles negative edge weights without complaint — the acyclicity, not the sign of the weights, is what makes it correct.
The same "process in dependency order" idea is exactly what makes dynamic programming on a DAG legal. Any DP is secretly a graph: subproblems are vertices, and an edge from subproblem a to subproblem b means b's answer needs a's. A valid evaluation order is precisely a topological order of that subproblem graph, and the DP has a well-defined answer if and only if the dependency graph is acyclic. So topological sort is not a niche graph trick — it is the structural reason the evaluation orders you met earlier in this ladder were allowed to exist.
Strongly connected components: clumps that reach each other
Topological order assumed there were no cycles. Strongly connected components face the cycles head on. In a directed graph, call two vertices u and v mutually reachable if there is a path from u to v and also a path back from v to u. A strongly connected component (SCC) is a maximal set of vertices that are all pairwise mutually reachable — a clump where you can get from anyone to anyone and back. A single vertex with no cycle through it is its own SCC of size one. The bigger SCCs are exactly the directed cycles, fused together where they overlap.
Here is the beautiful part. Collapse each SCC into a single super-vertex and draw an edge between two super-vertices whenever any edge crosses between their components. The result — the condensation — is always acyclic. It has to be: if the condensation had a cycle, all the SCCs on that cycle would be mutually reachable and would have merged into one bigger SCC in the first place, contradicting maximality. So every directed graph splits into SCCs whose condensation is a DAG, which means you can run a topological sort on the condensation. SCCs and topological order are the same toolkit: SCCs find the cycles, then the condensation hands you a DAG to order.
Finding SCCs: two passes of DFS
The most teachable SCC method, Kosaraju's algorithm, reuses everything above with a single new ingredient: the reverse graph, the same graph with every edge flipped. The reverse graph has exactly the same SCCs (mutual reachability does not care which way you label the arrows), but reversing the edges scrambles which components can reach which — and that scramble is precisely what lets a second DFS peel the components off one at a time.
- Run DFS over the whole graph and push each vertex onto a stack at its finish time — exactly the topological-order trick from before, even though the graph may now have cycles.
- Build the reverse graph by flipping every edge.
- Pop vertices off the stack in order; for each one not yet assigned, run a DFS in the reverse graph. Every vertex that DFS reaches forms exactly one SCC.
- Repeat until the stack is empty; the groups you carved out are the strongly connected components.
Why does popping by decreasing finish time and searching the reverse graph isolate one SCC at a time? The vertex with the largest finish time lives in a "source" SCC of the condensation — a component with no incoming cross-edges in the original graph. In the reverse graph those cross-edges point the other way, so from that vertex you can reach its own component but cannot escape into any other, and the DFS scoops up exactly that one SCC and stops. Remove it and the next unassigned vertex by finish time plays the same role for what remains. Each component is found in one bounded search, and the whole thing runs in O(V + E): two linear DFS passes plus the cost of reversing the edges, which on an adjacency list is itself O(V + E).