Can every task finish, given its prerequisites?

Count, for each task, how many rules still block it (its in-degree). Start with the unblocked tasks; each time one finishes, unblock the tasks that waited on it. If every task finishes, the rules allow an order. If some never become unblocked, they sit on a cycle or wait on one. O(V + E) time and space.

This is Kahn's algorithm for topological order; recording the finish order gives a valid schedule.

DFS with three colours (unvisited, in progress, done) finds cycles too: an edge to an in-progress node is a cycle.

Duplicate rules are fine as long as in-degrees count each copy.

from collections import deque


def can_finish(n: int, rules: list[list[int]]) -> bool:
    after: list[list[int]] = [[] for _ in range(n)]
    waiting = [0] * n
    for before, task in rules:
        after[before].append(task)
        waiting[task] += 1
    ready = deque(t for t in range(n) if waiting[t] == 0)
    done = 0
    while ready:
        t = ready.popleft()
        done += 1
        for nxt in after[t]:
            waiting[nxt] -= 1
            if waiting[nxt] == 0:
                ready.append(nxt)
    return done == n

fun canFinish(n: Int, rules: List<List<Int>>): Boolean {
    val after = List(n) { mutableListOf<Int>() }
    val waiting = IntArray(n)
    for ((before, task) in rules) {
        after[before].add(task)
        waiting[task]++
    }
    val ready = ArrayDeque((0 until n).filter { waiting[it] == 0 })
    var done = 0
    while (ready.isNotEmpty()) {
        val t = ready.removeFirst()
        done++
        for (nxt in after[t]) {
            waiting[nxt]--
            if (waiting[nxt] == 0) ready.addLast(nxt)
        }
    }
    return done == n
}

Common mistakes

• Treating the rules as undirected, which reports cycles that are not there.
• Reading [a, b] the wrong way round; check the direction with the interviewer.

Explain what leftover tasks mean (a cycle). That one sentence proves the algorithm is correct.

Follow-up questions

Think of your answer first, then open the hint.

1. How do you return a valid order?

   Show hint

   Append each task as it is taken from the queue.

2. What if you also want the fewest rounds when unblocked tasks run in parallel?

   Show hint

   Process the queue in layers; the number of layers is the answer.