Kahn Topological Sort: When to Use It

Start with the idea

A problem is a good match for Kahn Topological Sort when it asks for course schedules and build dependency order. Here the concrete task is: Return lexicographically smallest valid order. The visible input n=4 edges=0->1,0->2,1->3,2->3 is an example, not a definition of the whole problem. Ask what operations the solution must support and what the input guarantees. Choose a representation for the operations first; when traversing, DFS explores depth and BFS follows equal-cost layers. Directed edges and disconnected components change the plan. The right choice follows from those guarantees, not from a familiar noun in the prompt.

The decisive invariant is: Repeatedly remove zero-indegree nodes and decrement dependents; leftovers prove a cycle. Try to say why it applies to the task without quoting the implementation. Which fact becomes known after one update, and which possible answers remain? A graph method needs an explicit vertex-and-edge representation. For traversal, define when a vertex becomes seen: on insertion into the frontier or on removal. If that claim cannot be maintained on a legal input, the pattern is wrong or one of its preconditions is missing. A counterexample is more useful than a vague warning: change one property of the sample, trace the first two steps, and identify the exact claim that fails.

Compare costs before committing. The advertised bound is O(V+E) time · O(V) space; identify the operation responsible for it and the extra memory it needs.