Course Schedule

Hints

1. Translate before you compute. Courses are vertices and each prerequisite pair is a directed edge. The question "can I finish everything?" becomes "is this graph acyclic?". Everything else follows from that sentence.
2. Fix the edge direction and write it down. [a, b] means b comes first, so the edge points b -> a, and a gains an in-degree. Reversing this yields an algorithm that is internally consistent and answers the mirrored question, which is why it passes symmetric test cases and fails asymmetric ones.
3. Find the starting point. A course with no prerequisites, meaning in-degree zero, can be taken immediately. In a finite acyclic graph such a vertex always exists; if none exists, every vertex has an incoming edge and walking backwards must eventually repeat a vertex, which is a cycle.
4. Peel the graph. Take an in-degree-zero course, remove it, and decrement the in-degree of every course that listed it as a prerequisite. Anything that drops to zero becomes available. Keep going until nothing is available.
5. Decide by counting, not by inspection. If the peeling processed every course, the graph was acyclic. If it stalled with courses remaining, those courses form or depend on a cycle. One counter gives you the answer without ever searching for the cycle itself.
6. If you prefer DFS, use three states. Unvisited, on the current recursion stack, and fully finished. Meeting a vertex that is on the current stack is a back edge and therefore a cycle. Two states cannot distinguish "ancestor of the current node" from "already checked and safe", and that distinction is the whole cycle test in a directed graph.

Solution: two approaches

Approach 1 - Kahn's algorithm, BFS topological sort: O(V + E) time, O(V + E) space

Peel vertices with no remaining prerequisites and count how many you managed to remove.

from collections import deque

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

    for a, b in prerequisites:        # b must come before a
        graph[b].append(a)
        indegree[a] += 1

    queue = deque(i for i in range(num_courses) if indegree[i] == 0)
    processed = 0

    while queue:
        node = queue.popleft()
        processed += 1
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)

    return processed == num_courses

Why the final count decides it: a vertex is enqueued exactly once, at the moment its last prerequisite is removed, so processed equals the number of courses that could ever become available. In an acyclic graph every vertex eventually reaches in-degree zero, because its prerequisites form a finite chain that must bottom out. In a cyclic graph every member of the cycle is waiting on another member, so none of their in-degrees ever reaches zero and none is enqueued. Comparing the count against num_courses therefore tests acyclicity exactly, and it does so without ever identifying the cycle.

Why the edge direction is not a detail: writing graph[a].append(b) and incrementing indegree[b] builds the reverse graph. The reverse of a directed acyclic graph is also acyclic, so the algorithm still returns true for every valid input and false for every cycle, which is exactly why the bug survives the sample tests. It matters the moment a follow-up asks you to output the ordering, at which point the schedule comes out backwards.

Why it is O(V + E): building the adjacency list touches each of the E edges once. Each vertex is enqueued and dequeued at most once, giving O(V). When a vertex is dequeued, its outgoing edges are scanned once, and across the whole run each edge is scanned exactly once, giving O(E). Nothing is revisited, so the total is linear in the size of the graph. With the stated limits that is at most 2000 vertices and 5000 edges, trivially fast.

Why disconnected components need no special handling: the queue is seeded with every in-degree-zero vertex across the entire graph, not just those reachable from vertex 0. An isolated course starts at in-degree zero, is processed immediately, and counts towards the total. A solution that starts a traversal from a single source silently ignores whole components.

Approach 2 - DFS with three colours: O(V + E) time, O(V + E) space

Look for a back edge, an edge pointing at a vertex still on the current recursion stack.

def can_finish_dfs(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    for a, b in prerequisites:
        graph[b].append(a)

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

    def dfs(node):
        if state[node] == IN_STACK:       # back edge, cycle found
            return False
        if state[node] == DONE:           # already proved safe
            return True
        state[node] = IN_STACK
        for nxt in graph[node]:
            if not dfs(nxt):
                return False
        state[node] = DONE
        return True

    return all(dfs(i) for i in range(num_courses) if state[i] == UNVISITED)

Why two states are not enough: with only visited and unvisited, meeting a visited vertex is ambiguous. It might be an ancestor on the current path, which is a cycle, or a vertex explored and cleared during an earlier branch, which is perfectly legal. The diamond 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3 is acyclic, yet vertex 3 is reached twice, and a two-state solution reports a cycle. The third state records the distinction between "currently being explored" and "finished and safe".

Why DONE is what keeps it linear: without marking vertices finished, the same subtree is re-explored through every path that reaches it, and on a graph shaped like a chain of diamonds the work doubles at each level and becomes exponential. Setting DONE on the way out means each vertex is fully expanded once, so each edge is traversed once, giving O(V + E). This is memoisation of the predicate "no cycle is reachable from here".

Kahn's is usually the better answer to give first: it needs no recursion, so a 2000-vertex path cannot exhaust the stack, and the same code yields the actual ordering by recording the dequeue sequence. Reach for DFS when you need the cycle itself, since the recursion stack holds it at the moment of detection. BFS versus DFS works through when each is the better default.

Complexity comparison

Edge cases to verify

• No prerequisites: numCourses = 3, [] returns true. Every vertex seeds the queue on the first line.
• Two-cycle: [[1, 0], [0, 1]] returns false. The queue starts empty, processed stays 0.
• Cycle not reachable from vertex 0: numCourses = 4, [[1, 0], [2, 1], [3, 2], [1, 3]] returns false. Catches any traversal that starts only from a single source.
• Disconnected components: numCourses = 4, [[1, 0]] returns true, with courses 2 and 3 isolated and still counted.
• Self-loop: [[0, 0]] returns false. Vertex 0 has in-degree 1 from itself and is never enqueued.
• Long chain: 2000 courses in a line is valid, and deep enough to exhaust the default recursion limit in the DFS version.

Where beginners go wrong

• Reversing the edge direction. [a, b] means b -> a. Building the reverse graph still answers the acyclicity question correctly, because reversing a DAG yields a DAG, so the bug hides completely on this problem and surfaces the moment a follow-up asks for the ordering, which then comes out backwards.
• Using two states in the DFS. Visited and unvisited cannot tell an ancestor on the current path from a vertex already cleared. The acyclic diamond 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3 is reported as cyclic. Three states are not an optimisation; they are the correctness condition.
• Forgetting to mark vertices DONE. Without the finished marker the same subgraph is re-expanded through every path that reaches it, and on stacked diamonds the running time becomes exponential while the answer stays correct. A slow-but-right solution is the hardest kind to debug under time pressure.
• Traversing from a single starting course. The graph can be disconnected and the cycle need not be reachable from vertex 0. Kahn's handles this by seeding the queue with every in-degree-zero vertex; DFS handles it by looping over all vertices and starting from each unvisited one.
• Deciding by whether the queue emptied. The queue always empties; that is the loop condition. The decision is whether processed reached num_courses. Returning true because the loop finished reports success on every input.
• Rebuilding the in-degree array inside the loop. Recomputing in-degrees after each removal turns a linear algorithm into O(V * E). Decrement the counters incrementally as edges are consumed.

Interview follow-ups to expect

• "Return a valid order, not just a boolean." Course Schedule II. Append each dequeued vertex to a list; if the list reaches num_courses it is a valid topological order, otherwise return empty. Zero extra cost, which is one reason to present Kahn's first.
• "Which courses are involved in the cycle?" Whatever remains with non-zero in-degree after Kahn's stalls. Alternatively, catch it in the DFS: at the moment a back edge is found, the recursion stack holds the cycle from the repeated vertex downward.
• "Is the ordering unique?" Only if the queue never holds more than one vertex at a time. If it ever holds two, both are legal next choices and at least two distinct orderings exist. A one-line check inside the loop.
• "Courses run in semesters and you can take any number in parallel." The answer is the number of BFS levels, which is the longest path in the DAG. Process the queue level by level exactly as in a standard breadth-first traversal and count the rounds.
• "Each course has a duration; minimise total time." Longest path by weight through the DAG, computable in O(V + E) by relaxing edges in topological order. This is the critical path in project scheduling, and it is tractable only because the graph is acyclic.
• "New prerequisites arrive over time." Incremental cycle detection. Recomputing from scratch is O(V + E) per edge; maintaining a topological order under insertions is a well-studied problem with much better amortised bounds, and saying you would reach for that literature is a better answer than inventing one on the spot.

Related reading

• Topological Sort: the ordering that underlies this problem, and the proof that an in-degree-zero vertex always exists in a finite DAG.
• Graphs: the module this belongs to, including adjacency representations and their trade-offs.
• Number of Islands: traversal on an implicit undirected graph, where connectivity rather than ordering is the question.