Topological ordering

When to use it

Use it when pairs say one thing must come before another, and you need an order that keeps every pair, or need to know that no such order exists.

It belongs to the graphs group: Visit every place you can reach, once each, in the order that suits the question.

Watch it work

A town hall gives out 6 forms, numbered 0 to 5. A pair [a, b] says you must hold form a before you can get form b. Return the forms you can get, in an order that works. Some forms need each other, so nobody can get those.

Input
n = 6
pairs = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [4, 5], [5, 4]]

Output
[0, 1, 2, 3]

The method

1. For each form, list what needs it and count what it needs
2. Put every form that needs nothing in a queue
3. Take the form at the front and add it to the order
4. Each form that needs it now waits for one form fewer
5. A form that waits for nothing more joins the queue
6. Return the order; forms left out wait for each other

The run, one moment at a time

1. Step 1. An arrow from a to b says form a must come before form b. The row counts the forms each one waits for: form 3 waits for 2, and form 0 for none.

   waits for: 0 1 1 2 2 1
   queue: empty
   order: empty
   

2. Step 2. Only form 0 waits for nothing, so you can get it at once. It goes into the queue, a line where forms join at the back and leave from the front.

   waits for: 0 1 1 2 2 1
   queue: 0
   order: empty
   

3. Step 3. Take form 0 from the front of the queue. It needs nothing, so it is first in the order.

   waits for: 0 1 1 2 2 1
   queue: empty
   order: 0
   

4. Step 5. Forms 1 and 2 needed form 0. Each now waits for one form fewer, which is 0, so both join the queue.

   waits for: 0 0 0 2 2 1
   queue: 1 2
   order: 0
   

5. Step 3. Take form 1 from the front of the queue. Everything it needs is in the order already, so it comes next.

   waits for: 0 0 0 2 2 1
   queue: 2
   order: 0 1
   

6. Step 4. Form 3 needed form 1. Its count drops from 2 to 1. It still waits for form 2, so it does not join the queue.

   waits for: 0 0 0 1 2 1
   queue: 2
   order: 0 1
   

7. Step 3. Take form 2 from the front of the queue. Everything it needs is in the order already, so it comes next.

   waits for: 0 0 0 1 2 1
   queue: empty
   order: 0 1 2
   

8. Step 5. Form 3 needed form 2 too. Its count drops from 1 to 0: everything it needs is in the order, so it joins the queue.

   waits for: 0 0 0 0 2 1
   queue: 3
   order: 0 1 2
   

9. Step 3. Take form 3 from the front of the queue. Everything it needs is in the order already, so it comes next.

   waits for: 0 0 0 0 2 1
   queue: empty
   order: 0 1 2 3
   

10. Step 4. Form 4 needed form 3. Its count drops from 2 to 1. It still waits for form 5, so it does not join the queue.

    waits for: 0 0 0 0 1 1
    queue: empty
    order: 0 1 2 3
    

11. Step 6. The queue is empty and the order holds 4 of the 6 forms. Forms 4 and 5 each wait for the other, so neither count can reach 0. Nobody can get them.

    waits for: 0 0 0 0 1 1
    queue: empty
    order: 0 1 2 3
    

The code

The numbered comments are the steps of the method.

function solve(n, pairs) {
  // 1. For each form, list what needs it and count what it needs
  const after = Array.from({ length: n }, () => []);
  const waits = Array(n).fill(0);
  for (const [a, b] of pairs) {
    after[a].push(b);
    waits[b]++;
  }
  // 2. Put every form that needs nothing in a queue
  const queue = [];
  for (let form = 0; form < n; form++) {
    if (waits[form] === 0) queue.push(form);
  }
  // 3. Take the form at the front and add it to the order
  const order = [];
  // Taking from the front of an array is slow, so nothing is removed:
  // head is the position of the front.
  for (let head = 0; head < queue.length; head++) {
    const form = queue[head];
    order.push(form);
    // 4. Each form that needs it now waits for one form fewer
    for (const other of after[form]) {
      waits[other]--;
      // 5. A form that waits for nothing more joins the queue
      if (waits[other] === 0) queue.push(other);
    }
  }
  // 6. Return the order; forms left out wait for each other
  return order;
}

from collections import deque


def solve(n, pairs):
    # 1. For each form, list what needs it and count what it needs
    after = [[] for _ in range(n)]
    waits = [0] * n
    for a, b in pairs:
        after[a].append(b)
        waits[b] += 1
    # 2. Put every form that needs nothing in a queue
    # A deque is fast at both ends: append adds at the back,
    # popleft takes from the front.
    queue = deque()
    for form in range(n):
        if waits[form] == 0:
            queue.append(form)
    # 3. Take the form at the front and add it to the order
    order = []
    while queue:
        form = queue.popleft()
        order.append(form)
        # 4. Each form that needs it now waits for one form fewer
        for other in after[form]:
            waits[other] -= 1
            # 5. A form that waits for nothing more joins the queue
            if waits[other] == 0:
                queue.append(other)
    # 6. Return the order; forms left out wait for each other
    return order

How to spot it

Given: Each pair says one item must come before another

These are one-way requirements. Count for each item how many others must come first, and take the items whose count is 0.

Asked: Return an order in which everything can be done

Taking an item only when nothing it needs is missing builds such an order, from the front to the back.

Asked: Can all of it be done, true or false?

It can, unless some requirements form a loop. Items in a loop never reach a count of 0, so they are never taken.

Limits: Thousands of items and pairs, so trying every order is far too slow

Ten items already have 3,628,800 possible orders. This method reads each item once and each pair twice.

Looks like it, but is not

• You only need to know whether one item can be reached from another along the links. Use Graph traversal with a visited set. That is one walk from a start that marks what it reaches. No order of all the items is built.
• The requirements form a tree: a node's answer needs the answers of its children first. Use Postorder tree recursion. A tree already gives the order, children before their parent. Recursion visits them that way with no counts and no queue.
• You need the fewest steps from a start to a goal, and every step costs the same. Use Breadth-first search by distance. It also uses a queue, but places join it by distance from the start. Nothing waits for several others to be done first.

Cost and mistakes

Each item joins the queue at most once, and each pair is read twice. For n items and m pairs that is about n + m steps, written O(n + m). The lists and the counts need the same amount of space.

Watch out

• Check the length of the order at the end. If it holds fewer items than there are, some of them wait for each other in a loop, called a cycle, and no full order exists.
• Store each pair under the item that comes first. Problems often write a pair in the opposite order, as the item and then what it needs, so read the statement with care.

In the 150

3 problems of the 150 use it. Naming them gives their method away, so the list is folded.