Hints — p23 Course Schedule

Read one at a time.

Hint 1 — Translate to graph language. “Take a after b” = directed edge b → a. The whole problem becomes: “given this directed graph, is there a cycle?” A cycle means there’s a course that ultimately depends on itself — impossible to schedule.

Hint 2 — Two canonical algorithms. Either:

• Kahn’s: start from courses with NO prerequisites. Take them. Each course you take, “remove” its outgoing edges (decrement neighbors’ in-degree). When a neighbor’s in-degree hits 0, it joins the queue. If you process all N courses → no cycle.
• DFS 3-coloring: WHITE (untouched), GRAY (currently descending through), BLACK (fully processed). If DFS ever encounters a GRAY node, that’s a back-edge — cycle.

Hint 3 — Arrow direction is a trap. prereqs[i] = [a, b] means course b is a prerequisite of a. Is the edge a → b or b → a? Pick a convention and write it as a comment on line 1. (Hint: edges should point in the order you’d take the courses, so b → a.)

Hint 4 — Kahn’s correctness check. After the loop, you MUST verify processed_count == N. If a cycle exists, the queue runs dry early (no node ever reaches in-degree 0 inside the cycle). Don’t just return True when the loop ends.

Hint 5 — Don’t forget disconnected components. Initialize Kahn’s queue with EVERY zero-in-degree node, not just node 0. For DFS, your outer loop must call dfs(i) for every i that hasn’t been colored BLACK yet.

If still stuck: look at can_finish_kahns in solution.py — 15 lines, includes the critical processed == N check.