Return the Prerequisite Route for a Target Course

Problem Statement

You are given an integer num_courses, a list of prerequisite pairs prerequisites, and an integer target. Each prerequisite pair [a, b] indicates that course b must be taken before course a can be taken (b -> a).

Your task is to return a course plan containing only the target course and all of its direct and indirect prerequisites. The plan must satisfy the following conditions:

1. Relevance: Only include courses required to complete target (including target itself). Unrelated courses must be excluded.
2. Cycle Detection: If there is a circular dependency within the prerequisites required for target, return an empty list []. Any cycles among courses unrelated to target should be ignored.
3. Deduplication: There may be duplicate prerequisite pairs in prerequisites; these should be treated as a single dependency.
4. Determinism: Whenever multiple courses can be taken next, always pick the one with the smallest course ID.

Function Signature

def find_prerequisite_route(num_courses: int, prerequisites: list[list[int]], target: int) -> list[int]:
    pass

Constraints

• 1 <= num_courses <= 10^5
• 0 <= len(prerequisites) <= 2 * 10^5
• prerequisites[i].length == 2
• 0 <= a, b < num_courses
• 0 <= target < num_courses

Examples

Example 1

Input:
num_courses = 6
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2], [4, 5], [5, 4]]
target = 3

Output: [0, 1, 2, 3]

Explanation:
Course 3 requires courses 1 and 2. Both course 1 and course 2 require course 0.
The required courses are {0, 1, 2, 3}.
Although courses 4 and 5 form a cycle, they do not affect course 3 and are ignored.
At step 1: course 0 has in-degree 0. Take 0.
At step 2: courses 1 and 2 both have in-degree 0. 1 < 2, so take 1.
At step 3: course 2 has in-degree 0. Take 2.
At step 4: course 3 has in-degree 0. Take 3.

Example 2

Input:
num_courses = 4
prerequisites = [[1, 0], [2, 1], [0, 2]]
target = 2

Output: []

Explanation:
Course 2 depends on 1, which depends on 0, which depends on 2. This cycle prevents course 2 from being completed, so return [].

Example 3

Input:
num_courses = 3
prerequisites = []
target = 1

Output: [1]

Explanation:
Course 1 has no prerequisites, so the plan only contains [1].