Course Schedule (Cycle Detection)

Start from brute force

The obvious approach simulates semesters. Make a pass over every course and take any whose prerequisites are all already taken, by scanning prereqs for that course; repeat until a pass takes nothing, then check whether all n were taken. It is correct, because a course is taken exactly when nothing it depends on is still pending. But each pass costs O(V + E), and a chain listed in the worst order takes only one course per pass: with [[0, 1], [1, 2], [2, 3], [3, 4]] it needs five passes plus an empty one. That is O(V · (V + E)) time with O(V) space for the taken set, around 10¹⁰ steps at 10⁵ courses.

The approach

Kahn’s algorithm keeps the bookkeeping the brute force recomputes. The invariant is that indeg[v] is the number of v’s prerequisites not yet taken, so a course is takeable exactly when its count reaches 0, and nothing ever needs rescanning. A course on a cycle, or downstream of one, waits on a course that waits on it, so its count never reaches 0 and it is never taken.

The reference solution reads each pair [a, b] as an edge b → a: it appends a to adj[b] and adds 1 to indeg[a]. It seeds a deque with every course whose in-degree is 0. Each popleft() takes course u, adds 1 to taken, and decrements indeg[v] for every v in adj[u], appending v to the queue the moment its count hits 0, so each course is queued at most once. When the queue empties, taken == n is the answer: every course was released, or a cycle held some back.

Walk through an example

The first two examples are too small to show a course waiting on two prerequisites, so trace the diamond in example 3, can_finish(4, [[1, 0], [2, 0], [3, 1], [3, 2]]).

Complexity

Optimal (Kahn’s): O(V + E) time, since each course is queued and popped once and each edge is decremented once, and O(V + E) space for adj, indeg and the queue. The TypeScript reference uses Array.shift(), which can cost O(V) per call; a read index keeps it linear. Brute force (repeated passes): O(V · (V + E)) time, O(V) space.

Edge cases to test

• A course that requires itself: n = 1, prereqs = [[0, 0]] → False. indeg[0] is 1, and only course 0 could ever lower it.
• Duplicate pairs: n = 2, prereqs = [[1, 0], [1, 0]] → True. indeg[1] counts 2 and adj[0] lists 1 twice, so both decrements happen. Deduplicating adj but not indeg leaves course 1 stuck at 1 and returns False.
• No prerequisites: n = 3, prereqs = [] → True. Every course starts in the queue.
• A cycle in one component only: n = 4, prereqs = [[1, 0], [2, 3], [3, 2]] → False. Courses 0 and 1 are taken, 2 and 3 never are, so taken stops at 2.
• A course downstream of a cycle but not on it: n = 3, prereqs = [[1, 0], [0, 1], [2, 1]] → False. Course 2 is never released either.
• n = 0 → True: zero courses taken out of zero.

Common mistakes

• Not detecting the cycle — a circular prerequisite is unsatisfiable, and that is the whole question.
• Building adj and indeg in inconsistent directions, such as adj[a].append(b) with indeg[a] += 1: then can_finish(2, [[1, 0]]) returns False. Reversing both consistently is harmless for this yes/no question, because a graph and its reverse have the same cycles; it only matters when you return the order.
• In a DFS version, treating any already-visited node as a cycle. In the diamond 0 → 1 → 3, 0 → 2 → 3, course 3 is reached twice with no cycle; only a node still on the current path (gray) closes one.

Follow-ups an interviewer asks next

Can you return an actual order to take the courses in?

Yes, that is Course Schedule II. Append u to an order list each time it is popped; if len(order) == n, return it, otherwise return an empty list because a cycle exists. The pop order is a valid topological order, since a course enters the queue only after all its prerequisites were popped. Time and space stay O(V + E).

How would you solve it with DFS instead?

Color each node white (unvisited), gray (on the current path) or black (finished). Reaching a gray node means a back edge, which is a cycle. Reversed post-order gives a topological order. It is also O(V + E), but the recursion can go V deep, and Python’s default recursion limit is 1000, so a long chain needs an explicit stack.

How would you report which courses form the cycle?

After Kahn’s algorithm, the courses with indeg still above 0 are on a cycle or downstream of one. To print an actual cycle, run a DFS restricted to those leftover courses and keep the current path; the first edge back to a node on the path gives the loop, which is the message a package manager prints for a circular dependency.

What is the minimum number of semesters if you can take any number of courses at once?

Process Kahn’s queue level by level: everything in the queue at the start of a round is one semester. The number of rounds equals the number of courses on the longest prerequisite chain, and it is still O(V + E). Capping how many courses fit in a semester makes the problem much harder, which is why that variant is usually posed with very small n.

Where this shows up

This is topological sort — the “valid order under dependencies” behind build systems (make, Bazel), task schedulers, package managers resolving install order, and spreadsheet recalculation. Cycle detection is exactly why a circular dependency errors out instead of hanging forever.

Reference solution

from collections import deque

def can_finish(n, prereqs):
    indeg = [0] * n
    adj = [[] for _ in range(n)]
    for a, b in prereqs:          # b must come before a  (b -> a)
        adj[b].append(a)
        indeg[a] += 1

    queue = deque(i for i in range(n) if indeg[i] == 0)
    taken = 0
    while queue:
        u = queue.popleft()
        taken += 1
        for v in adj[u]:          # u unlocks v
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return taken == n             # all scheduled -> no cycle


print(can_finish(2, [[1, 0]]))          # -> True
print(can_finish(2, [[1, 0], [0, 1]]))  # -> False

function canFinish(n: number, prereqs: number[][]): boolean {
  const indeg = new Array(n).fill(0);
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of prereqs) {   // b must come before a  (b -> a)
    adj[b].push(a);
    indeg[a]++;
  }

  const queue: number[] = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);

  let taken = 0;
  while (queue.length) {
    const u = queue.shift()!;
    taken++;
    for (const v of adj[u]) {        // u unlocks v
      if (--indeg[v] === 0) queue.push(v);
    }
  }
  return taken === n;                // all scheduled -> no cycle
}

console.log(canFinish(2, [[1, 0]]));         // -> true
console.log(canFinish(2, [[1, 0], [0, 1]])); // -> false