An order you can actually take the courses in

Courses are numbered from 0. Each rule a b means course a needs course b finished first. Report an order in which every course can be taken. If no such order exists, report nothing at all.

When several courses are available at once, take the lowest-numbered one, so the answer is a single definite order.

Worked example#

Four courses, with 1 needing 0, 2 needing 0, and 3 needing both 1 and 2:

      0
     / \
    1   2
     \ /
      3

Only 0 is available at the start. Finishing it frees 1 and 2; take 1 first because it is lower. Finishing both frees 3. So the order is 0 1 2 3.

If instead 0 needed 1 and 1 needed 0, neither could ever be first, and the answer is empty.

The idea#

Count, for each course, how many things it is still waiting on. Anything waiting on nothing can be taken now, so put those in a queue.

Take one out, record it, and tell everything that was waiting on it that one of its blockers is done. Anything whose count reaches zero has just become available, so it joins the queue.

waiting_on[c] = how many prerequisites c still has
queue = every course with waiting_on == 0

while the queue is not empty:
    take c, record it
    for each course that needed c:
        waiting_on -= 1
        if it hits zero: add it to the queue

That is Kahn's algorithm, and it is breadth-first search with the "have I been here" test replaced by "is it ready yet".

Detecting the impossible#

The loop stops when nothing is ready. If it has recorded every course, the order is valid. If it stops early, the courses left over are all waiting on each other: a cycle, and no order exists.

Notice that you get this for free. There is no separate cycle check, because "some courses were never freed" is the cycle. That is the neat part of Kahn's, and it is why "can these courses be finished" and "is there a cycle" are the same question.

Making the answer definite#

With several courses ready at once, any of them could go next, so there are usually many valid orders. Taking the lowest-numbered one makes the answer unique, which is what lets a test check it. Real schedulers take whichever is cheapest or most urgent instead, and the algorithm does not care.

Constraints#

• 1 <= courses <= 2000
• 0 <= rules <= 5000, each naming two different courses

About the input#

The number of courses, then a rules grid: a row count, a column count of 2, then each rule as a b.