Topological Sort by Indegree

core

You are given a DAG on nodes 0 through n-1 as an adjacency list adj (adj[u] lists u's out-edges, in the order given). Implement topo(n, adj) using Kahn's algorithm with a plain FIFO queue, returning one topological order as a vector. To make the output deterministic, seed the queue before any processing with every node whose indegree is 0, in ascending order of index (0, 1, 2, ...), not just the first one found. While processing, when popping node u, scan adj[u] in the given order and decrement the indegree of each destination, pushing a destination the moment its indegree reaches 0. Assume the input is a DAG; you do not need to detect cycles.

Example: topo(4, {{2}, {2}, {3}, {}}) (edges 0->2, 1->2, 2->3) has two nodes with indegree 0 (0 and 1), seeded in ascending order. Processing 0 drops node 2's indegree to 1 (not yet queued); processing 1 drops it to 0, queuing it; processing 2 then queues 3. Result: {0, 1, 2, 3}.

Input format: each test in tests/*.in is laid out as:

Line 1: n e, the node count and the number of directed edges; nodes are numbered 0 to n - 1.
Next e lines: u v, one directed edge from u to v. When e is 0 the file is just the header line.

Test 03.in reads:

3 2
1 0
2 0

This is 3 nodes and 2 edges, 1 -> 0 and 2 -> 0: both 1 and 2 start with in-degree 0 and must come out before 0.

Where you'll use it:

✦ Solution & editorial unlock with the pass.