Phase 1: Bridge from Course Schedule I — recognize the hidden computation

You Already Have Most of the Answer

I wrote Course Schedule II as a completely new function before realizing it was the same function with one extra line. I spent twenty minutes rethinking the algorithm from scratch. The extra line was result.push(node). That was the entire difference between detecting feasibility and producing a valid schedule.

Course Schedule I built a cycle detector. It told you “yes, all courses can be taken” or “no, a cycle exists.” What it never told you was WHICH order to take them. Course Schedule II asks exactly that: given the same prerequisite graph, return a valid order of all courses. If it's impossible, return an empty array.

The graph below has 4 courses. Course 1 requires Course 0. Course 2 requires Course 0. Course 3 requires both Course 1 and Course 2 — a diamond dependency. Both 0123 and 0213 are valid orderings. Any order that puts Course 0 before Courses 1 and 2, and both of those before Course 3, satisfies all prerequisites. The question is: does your algorithm naturally produce such an order, or do you need to invent a new one?

Course Schedule I's algorithm — DFS 3-color — was already doing more work than you realized. It was exploring every course, following every prerequisite edge, finishing courses in a specific order. The order in which it finishes courses is exactly the reverse of a valid topological ordering. It was computing the answer the whole time. You were just not recording it.

The metaphor: the registrar at your university processes your graduation request. To answer “can you graduate?”, they trace through all your course prerequisites. By the time they have an answer, they have implicitly computed a valid schedule. Course Schedule I is a registrar who says “yes” and throws away their work. Course Schedule II is a registrar who says “yes, and here is the schedule I just computed.”

The challenge here is not algorithmic — it is perceptual. You have to look at an algorithm you already know and notice what it was doing that you were not paying attention to. The finish order was always there. You just did not record it.

Course Schedule I's DFS already visits every course in some order. What does that visitation order tell you about the topological order?