Course Schedule: Topological Sort Detects the Cycle

Course Schedule asks whether you can finish numCourses courses given prerequisite pairs [a, b] meaning "b before a." It is a directed graph. An edge b → a means b must come first. You can finish if and only if the graph has no cycle.

Interviewers are not asking you to print a schedule. They are asking whether you notice a cycle, and whether you can say so without hand-waving DFS colors you do not finish writing.

Kahn's algorithm

Count how many prerequisites each course still has. Every course with indegree 0 is ready. Take one, reduce the indegree of what depends on it, and repeat. If you process every course, there was no cycle. If some remain with indegree above 0, those are stuck in a cycle.

from collections import defaultdict, deque

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    indegree = [0] * numCourses
    graph = defaultdict(list)
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    ready = deque(i for i in range(numCourses) if indegree[i] == 0)
    taken = 0
    while ready:
        prereq = ready.popleft()
        taken += 1
        for course in graph[prereq]:
            indegree[course] -= 1
            if indegree[course] == 0:
                ready.append(course)
    return taken == numCourses

Time is O(V + E). Space is O(V + E) for the adjacency list and the queue. V is numCourses. E is the number of pairs.

The case they add if you go quiet

A self-loop, [0, 0], is a cycle of one. Indegree of 0 starts at 1, nothing is ready that can unlock it, taken stays short of numCourses. You do not need a special case.

Two nodes pointing at each other, and a third course with no edges, must return false. The isolated course is taken. The pair is not. Counting only the isolated node and returning true is the off-by-one people ship when they return taken > 0.

Course Schedule II asks for one valid order. Same loop. Append prereq to an output list as you pop it. If taken != numCourses, return an empty list. The order you appended is one topological order, not the only one. Say that. Interviewers who want a specific order will add a tie-break. Do not invent one.

DFS with three colors (unvisited, on the stack, done) is the other correct answer. Use it if you are already comfortable and can explain "a back edge to a node on the stack is a cycle" in one sentence. Kahn's algorithm is easier to finish on a whiteboard because the queue is the whole story.