Return the Prerequisite Route for a Target Course
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
A directed graph describes course prerequisites. For one target course, return a valid order containing exactly the target and every direct or indirect prerequisite it requires. Courses unrelated to the target must not appear.
## Function Contract
Implement `target_course_plan(num_courses, prerequisites, target)` and return a list of course IDs.
## Rules
- Each pair `[course, prerequisite]` means the prerequisite must be completed before the course.
- If several courses are currently available, choose the smallest ID so the answer is canonical.
- Return an empty list if the subgraph required by the target contains a cycle.
- Ignore cycles and edges in components that cannot reach the target.
## Constraints
- `1 <= num_courses <= 200000`.
- Course IDs are integers in `[0, num_courses - 1]`.
- `0 <= len(prerequisites) <= 400000`.
- Duplicate prerequisite pairs may appear and must not change the answer.
## Examples
```text
num_courses = 7
prerequisites = [[4, 2], [4, 3], [2, 1], [6, 5]]
target = 4
output = [1, 2, 3, 4]
```
Courses 5 and 6 are unrelated and are excluded.
Quick Answer: Return a deterministic course plan containing one target and exactly its direct and indirect prerequisites. Restrict cycle detection to the required subgraph, exclude unrelated courses, deduplicate edges, and choose the smallest available course whenever several orders are valid.
A directed prerequisite graph contains courses numbered from 0 through num_courses - 1. Each pair [course, prerequisite] means the prerequisite must be completed before the course. For target, return a valid order containing exactly the target and all of its direct or indirect prerequisites; exclude unrelated courses. Whenever several required courses are available, choose the smallest ID. Return an empty list if the subgraph required by target contains a cycle. Ignore cycles and edges in components that cannot reach target, and treat duplicate pairs as one edge.
Constraints
- 1 <= num_courses <= 200000.
- 0 <= len(prerequisites) <= 400000.
- Every course ID and target is an integer in [0, num_courses - 1].
- Duplicate prerequisite pairs do not change the answer.
Examples
Input: (7, [[4, 2], [4, 3], [2, 1], [6, 5]], 4)
Expected Output: [1, 2, 3, 4]
Explanation: Only prerequisites that lead to target 4 are included in smallest-available order.
Input: (3, [], 2)
Expected Output: [2]
Explanation: A target without prerequisites is the complete one-course plan.
Hints
- First follow prerequisite edges backward from target to isolate the required subgraph.
- Topologically order only that closure with a smallest-first frontier.