Put tasks in an order where every task comes after the tasks it depends on.
The idea (getting dressed)
You cannot put on shoes before socks, or a jacket before a shirt. Each arrow A → B means “A must happen before B”. A topological sort lists everything in an order that respects every arrow. Course prerequisites, build systems and task schedulers all need this.
Kahn’s algorithm does it by repeatedly doing what is allowed right now:
For every task, count how many things it still waits for. This count is its indegree (arrows coming in).
Tasks with indegree 0 wait for nothing. Put them in a queue.
Take a task from the queue and add it to the answer. Then “cross out” its arrows: every task that waited on it now has one fewer thing to wait for. If a task reaches 0, queue it.
If you run out of tasks to take but some are still waiting, they are waiting on each other: that is a cycle, and no valid order exists.
Watch it work
Tasks are numbered from 0. At most 15 arrows.
Try it
Run the default. There can be several valid orders; this one is the queue’s choice. Check that every arrow points forward in the answer.
Add an arrow that makes a loop, like 1>5. What happens, and which nodes get stuck?
Remove all arrows. In what order do the tasks come out?
Make a straight chain 0>1, 1>2, 2>3. How many valid orders exist?
Common mistakes
Not checking for a cycle. If len(order) != n the input has a cycle, and you must report that instead of a partial order.
Mixing up the arrow direction. Decide what “A→B” means before coding (“A before B” vs “B needs A”). Many course problems list pairs as [course, prerequisite], which is the reverse.
Forgetting isolated nodes. Tasks with no arrows have indegree 0 and must still appear in the answer.
Assuming the answer is unique. Usually many valid orders exist. Tests must check validity, not one exact list.
Complexity, in plain English: every task enters the queue at most once and every arrow is crossed out once, so the time is about the tasks plus the arrows (O(V + E)).