Course Schedule

Course Schedule asks a yes/no question hiding a classic graph idea: given courses and their prerequisites, can you order them so every course comes after the ones it depends on? You can — unless the prerequisites loop back on themselves. Detecting that loop is topological sort.

The idea

Think of the courses as a directed graph: draw an arrow from pre to course. "Can I finish everything?" becomes "does this graph have a cycle?" If course A needs B and B needs A, you are stuck forever — that loop is the only thing that makes the answer false.

Kahn's algorithm finds the loop by trying to peel the graph apart, layer by layer:

• For each course, count its in-degree — how many arrows point into it. That is how many prerequisites it still has waiting.
• A course with in-degree 0 has no unmet prerequisites, so it is ready — you can take it now. Put all such courses in a queue.
• Repeatedly take a ready course, mark it finished, and "remove" it: for every course it pointed to, drop one prerequisite (decrement its in-degree). If that drops a neighbor to 0, it becomes ready too.

If you manage to finish all num courses this way, there was no cycle. If the queue empties early — some courses never reached in-degree 0 — those courses are tangled in a loop, so the answer is false.

The key insight: a course is safe to finish the moment its in-degree hits 0, because that means every prerequisite has already been finished ahead of it.

Walk through it

Step through the animation. Each node's badge is its current in-degree. We seed the queue with course 0 (the only in-degree-0 course), finish it, and watch its arrows disappear — that drops 1 and 2 to 0, so they join the queue. Finishing 1 and 2 drops 3 to 0 last of all. The done counter climbs to 4, which equals num, so we return true.

Pseudocode

compute in-degree of every course (arrows pointing in)
queue = all courses whose in-degree is 0
done = 0
while queue is not empty:
    take a course off the queue
    done = done + 1
    for each neighbor it points to:
        decrement that neighbor's in-degree
        if the neighbor's in-degree is now 0:
            add it to the queue
return (done == number of courses)

The Python solution

def can_finish(num, prerequisites):
    indeg = [0] * num
    adj = [[] for _ in range(num)]
    for course, pre in prerequisites:
        adj[pre].append(course)
        indeg[course] += 1
    queue = [c for c in range(num) if indeg[c] == 0]
    done = 0
    while queue:
        node = queue.pop(0)
        done += 1
        for nxt in adj[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                queue.append(nxt)
    return done == num

• indeg[c] is how many prerequisites course c still has; adj[pre] lists the courses that depend on pre. We build both in one pass over prerequisites.
• queue starts with every course that already has in-degree 0 — the courses ready from the very start.
• The while loop is the heart: pop a ready course, count it as done, then walk its neighbors and decrement each in-degree. A neighbor that reaches 0 is now ready, so it goes on the queue.
• At the end, done == num is true only if every course came off the queue. If a cycle trapped some courses, they never reached in-degree 0, done falls short, and we return false.

Complexity

V is the number of courses and E the number of prerequisite pairs. We touch each course once and each arrow once, so the whole thing is O(V + E) time and space.

When this pattern shows up

Practice