• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i] = [a, b] means b is a prerequisite of a
• All prerequisite pairs are distinct
• A course may have any number of prerequisites, including none

Strip the story away first. Courses are things, prerequisites are one-way constraints between them, and the question is whether all the constraints can be satisfied at once. That is a graph question, and identifying the graph correctly is most of the battle.

Each course becomes a vertex. Each prerequisite pair becomes a directed edge, and the direction is where people go wrong.

The pair [a, b] means b must come before a. So the useful edge is b → a, read as "finishing b unlocks a". Building it as a → b instead reverses every relationship — and here is the nasty part: on many test cases a reversed graph still gives the right answer, because a graph has a cycle exactly when its reversal has a cycle. It passes, then fails on the ordering follow-up. Get the direction right on principle, not by testing.

With the graph built, the question becomes: is this directed graph free of cycles? A schedule exists precisely when it is. If courses x, y and z each require the next around a loop, none can ever be first, so none can ever be taken — and no amount of scheduling cleverness fixes it.

Rather than hunting for a cycle directly, simulate the student's experience and see how far you get.

Give each course a counter of how many prerequisites it still needs — its in-degree. A course with a count of zero can be taken immediately. Take it, and every course that listed it as a prerequisite loses one requirement. Any that drop to zero have just been unlocked and can be taken next. Keep going until nothing is available.

Then compare: if the number of courses you managed to take equals the total, every course was reachable and the answer is true. If you fall short, the leftovers are stuck.

Why is falling short a proof of a cycle rather than just a symptom? Every unfinished course still has at least one prerequisite that was never finished. Walk backwards from any unfinished course to one of its unfinished prerequisites, then to one of its, and so on. Each step lands on another unfinished course, and there are finitely many, so the walk must eventually revisit one — that repetition is exactly a cycle. So the count is a complete test, not a heuristic.

from collections import deque

def can_finish(num_courses, prerequisites):
    adj = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses

    for course, prereq in prerequisites:      # [a, b] means b before a
        adj[prereq].append(course)            # finishing prereq unlocks course
        in_degree[course] += 1

    queue = deque(c for c in range(num_courses) if in_degree[c] == 0)
    finished = 0

    while queue:
        course = queue.popleft()
        finished += 1
        for nxt in adj[course]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)

    return finished == num_courses

Each course enters the queue at most once and each edge is examined once, so this is O(V + E) time — with V up to 2000 and E up to 5000, entirely comfortable — and O(V + E) space for the adjacency list.

A depth-first search can detect the cycle directly, and it is worth knowing because the same machinery reconstructs the cycle when asked.

The naive idea — flag a cycle whenever you reach an already-visited course — is wrong, and understanding why is the valuable part. Consider courses where 0 unlocks both 1 and 2, and both 1 and 2 unlock 3. Exploring from 0 through 1 reaches 3. Backtracking and exploring through 2 reaches 3 again — already visited, yet there is no cycle here at all. Every path runs forward; 3 simply has two prerequisites.

The fix is to distinguish two different meanings of "seen". A course may be currently in progress, meaning it sits on the path you are exploring right now, or finished, meaning it and everything beyond it were fully checked and cleared. Reaching an in-progress course means the path has looped back onto its own ancestor — a genuine cycle. Reaching a finished course means nothing at all; skip it.

def can_finish(num_courses, prerequisites):
    adj = [[] for _ in range(num_courses)]
    for course, prereq in prerequisites:
        adj[prereq].append(course)

    UNVISITED, IN_PROGRESS, DONE = 0, 1, 2
    state = [UNVISITED] * num_courses

    def has_cycle(u):
        state[u] = IN_PROGRESS
        for v in adj[u]:
            if state[v] == IN_PROGRESS:       # looped back onto the current path
                return True
            if state[v] == UNVISITED and has_cycle(v):
                return True
        state[u] = DONE                       # cleared: safe forever
        return False

    return not any(has_cycle(c) for c in range(num_courses) if state[c] == UNVISITED)

The DONE state is what keeps this linear. Without it, a course reachable by many routes would be re-explored once per route, and the running time would blow up exponentially even though the answer stayed correct.

Take numCourses = 4 with prerequisites [[1,0], [2,1], [3,2], [1,3]].

Reading each pair as [course, prereq], the edges are 0→1, 1→2, 2→3 and 3→1. In-degrees: course 0 has none, so 0. Course 1 is pointed at by 0 and 3, so 2. Course 2 is pointed at by 1, so 1. Course 3 is pointed at by 2, so 1.

Finished is 1, but there are 4 courses, so the answer is false. And the leftover set {1, 2, 3} is exactly the cycle: 1 needs 3, 3 needs 2, 2 needs 1. Course 0 was perfectly takeable; one bad loop elsewhere still sinks the whole schedule.

Contrast with numCourses = 2 and prerequisites [[1,0]]. In-degrees are 0 for course 0 and 1 for course 1. Pop 0, finished is 1, course 1 drops to 0 and is enqueued. Pop 1, finished is 2. Two of two, so true.

This problem is a directed cycle detection question with a story attached, and recognising that is the whole skill. The signals recur constantly: prerequisites, dependencies, build order, task requirements, "must happen before" — all of it means a directed graph, and asking whether the work is completable means asking whether that graph is acyclic.

The two solutions are worth holding onto for different reasons. Kahn's counting version is easier to get right under pressure and generalises immediately to producing the actual schedule, which is the standard follow-up: collect the popped courses instead of just counting them. The DFS version generalises in a different direction — the in-progress states on the stack at the moment a cycle is found are the cycle, so it is the one to reach for when asked which courses are deadlocked.

Train the reflex: whenever a problem asks whether a set of "X before Y" requirements can all be satisfied, do not look for a clever scheduling rule. Build the directed graph and test it for a cycle.