185. Topological Sort of a Directed Acyclic Graph

Given a directed acyclic graph with n vertices (0-indexed) and m edges, print a valid topological order of its vertices, space-separated. Since multiple valid orders can exist, use Kahn's algorithm and always process the smallest-numbered vertex among those currently available (in-degree 0).

Input: The first line contains n, the number of vertices. The second line contains m, the number of edges. Each of the next m lines contains two integers u v, a directed edge. Output: Print a single line with the n vertices in topological order, space-separated.

1 <= n <= 10^5

Using a MIN-PRIORITY-QUEUE (not a plain FIFO queue) is specifically what this problem requires for its deterministic 'smallest-numbered vertex first' tie-breaking rule - a plain queue would give A valid topological order, but not necessarily the SPECIFIC one this problem's example expects.

Find a valid ordering of a DAG's vertices so every edge points from earlier to later in the ordering. Brute force: Try every possible permutation of vertices and check if it respects every edge's direction - this is factorial time, completely impractical. Optimised: Kahn's algorithm processes vertices in a way that guarantees every prerequisite is handled before its dependents, by only ever making a vertex 'available' once ALL its incoming edges have been accounted for - using a min-priority-queue instead of a plain queue additionally guarantees a deterministic, tie-broken-by-smallest-vertex output.

Use the same Kahn's algorithm, but keep available (in-degree-zero) vertices in a binary min-heap (priority queue) instead of a balanced tree set. Extracting the smallest available vertex and inserting newly-available ones are both O(log n), matching the ordered-set approach's complexity, but a binary heap has simpler, more cache-friendly array-backed operations with lower constant factors than a balanced BST, making it the standard, most practically efficient implementation of this exact algorithm. Time: O((n + m) log n) Space: O(n + m)

Compute the in-degree of every vertex. Then repeat n times: scan all n vertices from smallest to largest index, find the smallest-numbered vertex that currently has in-degree 0 and hasn't been output yet, output it, and decrement the in-degree of all its outgoing neighbors. Scanning all n vertices on every one of the n steps directly implements 'always pick the smallest available vertex' but is quadratic in the number of vertices. Time: O(n^2 + m) Space: O(n + m)

Run the standard Kahn's algorithm (process vertices whose in-degree has dropped to 0, decrementing neighbors' in-degrees as you go), but keep the currently-available (in-degree-zero) vertices in a balanced ordered set such as a TreeSet, which supports retrieving and removing the minimum element in O(log n) and inserting newly-available vertices in O(log n). This still always picks the smallest-numbered available vertex, but replaces the O(n) full rescans of the brute-force approach with O(log n) set operations. Time: O((n + m) log n) Space: O(n + m)

1. Compute every vertex's IN-DEGREE (number of incoming edges). 2. Start with all IN-DEGREE-0 vertices (nothing depends on them being done first) in a MIN-PRIORITY-QUEUE, so ties always resolve to the smallest vertex number. 3. Repeatedly pop the smallest available vertex, add it to the result, and DECREMENT its neighbors' in-degrees - any neighbor dropping to 0 gets added to the same priority queue.

Time: O((n + m) log n) using a min-priority-queue instead of a plain queue (the log n factor comes from the heap operations); O(n + m) with a plain queue if a specific tie-break order isn't required. Space: O(n), for the in-degree array and the priority queue.

Test a graph with multiple valid topological orders (must resolve ties by always picking the smallest available vertex), m = 0 (any permutation is valid, so ties resolve to 0..n-1), and n at the upper bound of 10^5.

Be ready to mention DFS-based topological sort (using finish times, pushed onto a stack) as an equally valid alternative to Kahn's algorithm - useful to know both, since some problems' constraints favor one over the other.