Course Schedule

Learning goal: Translate course prerequisites into a graph question about whether every vertex can be processed.

Core idea Treat each course as a node. For a prerequisite pair [a, b], draw a directed edge from b to a: completing b unlocks a. The central observation is that all courses are finishable exactly when this directed graph has no cycle. A cycle means every course in that loop is waiting for another course in the same loop.

Algorithm plan

• Create one graph node for each course.
• Add an edge from each prerequisite to the course it unlocks.
• Track each course's in-degree, the number of prerequisites still pointing into it.
• Repeatedly process courses whose in-degree is zero.
• Return whether the number of processed courses equals numCourses.

Micro-example For [[1,0],[2,0],[3,1],[3,2]], the edges are 0 → 1, 0 → 2, 1 → 3, and 2 → 3. Course 0 has no incoming edge, so it is a safe starting point.

Pitfalls

• Reverse the edge direction by accident: b → a means b unlocks a.
• Confuse a valid branching graph with a cycle; multiple outgoing edges are allowed.
• Stop after finding one available course instead of processing the entire queue.

Recap

• Prerequisites form a directed graph.
• A cycle is the only structural reason completion is impossible.
• Kahn's algorithm exposes cycles through leftover nodes.

Learning goal: Understand why repeatedly removing zero-in-degree nodes is a topological sort and why it detects cycles.

Core idea A course with in-degree = 0 has no uncompleted prerequisites, so it can safely be taken next. After taking it, remove its outgoing edges because it no longer blocks its dependent courses. If a cycle remains, every node in that cycle still has an incoming edge from another remaining node, so the process gets stuck.

Data structure model

Use three pieces of state:

• graph[u]: the courses unlocked by course u.
• inDegree[v]: how many prerequisites course v still needs.
• queue: courses currently available to take.

Micro-example Initially, only course 0 has in-degree = 0, so the queue is [0]. Removing 0 changes the in-degrees of 1 and 2 from 1 to 0, making both available.

Pitfalls

• A course entering the queue means all of its prerequisites are cleared, not that it is already processed.
• Do not infer a cycle merely because the graph branches or converges.
• Count processed courses, rather than assuming the queue length proves success.

Recap

• Zero in-degree means “ready now.”
• Removing a node can unlock its neighbors.
• A nonempty remainder after the queue empties is a cycle witness.

Learning goal: Implement the linear-time topological-sort approach and distinguish it from DFS cycle detection.

Core idea Kahn's algorithm is a breadth-first process over availability. Build the adjacency list and in-degree array, enqueue every zero-in-degree course, then repeatedly dequeue one course and decrement the in-degree of its neighbors. The algorithm succeeds when all V courses are removed.

Algorithm plan

build graph and inDegree
queue every course with inDegree == 0
processed = 0
while queue is not empty:
    course = dequeue()
    processed += 1
    for next in graph[course]:
        inDegree[next] -= 1
        if inDegree[next] == 0:
            enqueue(next)
return processed == numCourses

A DFS solution uses three states: unvisited, fully visited, and currently on the recursion stack. Encountering an on-stack node identifies a back edge and therefore a cycle. Kahn's algorithm and DFS answer the same structural question with different traversal mechanics.

Micro-example After processing 0, the queue contains 1 and 2. Processing both reduces inDegree[3] from 2 to 0, so 3 becomes the final available course.

Pitfalls

• Forgetting to decrement every outgoing neighbor.
• Returning true merely because the initial queue is nonempty.
• In DFS, treating “visited before” as equivalent to “on the current path.”

Recap

• Kahn's algorithm counts removals.
• DFS detects a back edge using an on-stack state.
• Both run in O(V + E) time with adjacency-list storage.

Learning goal: Trace Kahn's algorithm on the example and verify the final completion decision.

Core idea The queue contains exactly the courses that are currently legal to take. The in-degree values represent unmet prerequisites, so every decrement has a direct meaning: one prerequisite has just been completed. We preserve the invariant that no course enters the queue until all of its incoming edges have been removed.

Algorithm plan

• Initialize inDegree = [0,1,1,2] for courses 0 through 3.
• Enqueue course 0 because its in-degree is zero.
• Remove 0 and unlock 1 and 2.
• Remove 1 and 2; together they unlock 3.
• Remove 3 and compare the processed count with 4.

Micro-example The removal order is 0, 1, 2, 3. Every course is removed, so processed = 4 = numCourses and the answer is true.

Pitfalls

• Course 3 cannot be enqueued after processing only course 1; it still depends on course 2.
• The order between courses 1 and 2 is flexible because they are independent once 0 is removed.
• A valid answer is a boolean; constructing the full order is useful for explanation but not required.

Recap

• Queue state records immediate choices.
• In-degree reaches zero only after all prerequisites are removed.
• Four removals for four courses means true.

Learning goal: Avoid the most common cycle-detection mistake and recognize important graph edge cases.

Core idea BFS detects a cycle when some nodes can never reach in-degree zero. DFS needs more careful bookkeeping: visited answers whether a node has ever been explored, while onStack answers whether it belongs to the current recursive path. Only an edge to an onStack node proves a cycle during DFS.

Data structure model

For DFS, assign one of three states:

• 0: unvisited.
• 1: currently in the recursion path.
• 2: completely explored with no cycle below it.

When exploring u → v, recurse if v is unvisited, reject if v is on the current path, and skip if v is fully explored.

Micro-example For 0 → 1 and 1 → 0, DFS visits 0, then 1, then sees 0 with state 1. That back edge returns to the active recursion path, so the graph is cyclic.

Pitfalls

• Do not conflate visited with “in the current DFS path.” A node may be visited and fully finished without forming a cycle with the current branch.
• An isolated course has in-degree zero and should be processed normally.
• Duplicate prerequisite pairs should not cause a false success; each stored edge must be represented consistently.
• In an all-cycle graph, the initial queue may be empty; that immediately implies failure.

Recap

• visited is historical; onStack is active-path state.
• Self-dependencies and longer directed loops are cycles.
• Disconnected components must all be checked.

Learning goal: Justify the linear complexity and leave with a reliable implementation checklist.

Core idea Each course enters the queue at most once, and each prerequisite edge is examined exactly once when its source course is removed. Building the graph also touches every course and prerequisite once. Therefore the total work grows linearly with the graph size.

Algorithm plan

1. Allocate an adjacency list for all V courses.
2. For each pair [course, prerequisite], add course to the prerequisite's neighbors and increment inDegree[course].
3. Enqueue all courses with zero in-degree.
4. Remove courses, decrement neighbors, and enqueue newly unlocked courses.
5. Return processed == V.

Micro-example With V = 4 and E = 4, the example builds four nodes and four edges, then processes each node and edge once. The result is true because processed = V.

Pitfalls

• Saying the algorithm is O(V) while ignoring the E edge scans.
• Using an adjacency matrix, which can require O(V^2) space.
• Forgetting that the queue itself can contain many courses.

Recap

• Time: O(V + E).
• Space: O(V + E) for the graph, in-degrees, and queue.
• Complete removal is equivalent to the existence of a valid course order.