A DAG — a directed acyclic graph — is a directed graph with no cycles: follow the arrows and you can never return to a node you've already left. DAGs model anything with one-way dependencies: course prerequisites, build steps, task scheduling, "this must happen before that."
A topological ordering lists the nodes so that every node comes before all the
nodes it points to. If a → b (a must come before b), then a appears earlier in the
list. It's a valid order to do the tasks: never start something before its
prerequisites are done.
Such an ordering exists only for a DAG. A cycle a → b → c → a is a contradiction —
each would have to come before the other — so no valid order exists. That's the whole
reason topological sort requires acyclicity.
A node's in-degree is how many edges point into it — how many prerequisites it has. A node with in-degree 0 has nothing blocking it, so it's safe to place next:
// 1. compute in-degree of every node
// 2. start with all in-degree-0 nodes "ready"
// 3. repeatedly:
// take a ready node, append it to the output
// for each neighbour, decrement its in-degree;
// if it hits 0, it becomes ready
Each edge is processed once, so it's O(V + E). If you finish having output fewer than all nodes, some never reached in-degree 0 — that means a cycle exists (the graph wasn't a DAG). When several nodes are ready at once you may pick any of them; picking the smallest each time (as the next problem asks) gives the unique lexicographically smallest order.
The next problem, Topological Order, implements exactly this.