Prerequisite Route to a Target Course
Courses are numbered 0 to numCourses - 1. Each pair [course, prerequisite] means the prerequisite must be finished before the course. Pairs may repeat; a repeated pair is one edge.
For one target, return an order containing exactly the target and every course it depends on, directly or indirectly, with every prerequisite before the courses that need it. Whenever several of those courses could come next, take the smallest number. Courses the target does not depend on are left out — including any cycles among them. If the courses the target needs contain a cycle, return [].
prerequisiteRoute(7, [[4, 2], [4, 3], [2, 1], [6, 5]], 4) -> [1, 2, 3, 4] prerequisiteRoute(3, [], 2) -> [2]
After 1, both 2 and 3 are available; 2 is smaller, so it goes first. Courses 5 and 6 play no part.
Hints
Hint 1
Two passes: first find the set of courses the target needs (a search from the target along prerequisite edges), then order only that set.
Hint 2
Kahn's algorithm with a min-heap instead of a queue takes the smallest available course each time; count what came out to detect a cycle.