Produce valid student lineup from parent array

Problem: Lexicographical Student Lineup

You are given an array parents, where parents[i] represents the ID of the parent of student i. A value of -1 in parents indicates that student i has no parent (they are a root). A valid lineup is defined as an ordering of all students such that for every student, their parent appears earlier in the sequence than the student themselves.

Your task is to return the lexicographically smallest valid lineup of all students. If multiple valid lineups satisfy the parent-child constraints, you must choose the one that is lexicographically smallest at the first index where they differ.

Function Signature

def get_lexicographical_lineup(parents: List[int]) -> List[int]:

Constraints

• n = length of parents, where 1 <= n <= 10^5.
• Student IDs are represented by their index 0 to n-1.
• Each student has at most one parent.
• The input is guaranteed to form one or more valid rooted trees (a forest).

Example 1

Input: parents = [-1, 0, 0, 1] Output: [0, 1, 2, 3] Explanation: 0 is the root. 0's children are 1 and 2. 1's child is 3. The valid orderings include [0, 1, 2, 3] and [0, 1, 3, 2] and [0, 2, 1, 3]. The lexicographically smallest is [0, 1, 2, 3].

Example 2

Input: parents = [1, -1, 1] Output: [1, 0, 2] Explanation: 1 is the root, 1's children are 0 and 2. To keep the sequence lexicographically smallest, we pick the smallest child (0) before the larger child (2).