Dependency-Safe Deletion Order

Problem Statement

You are managing a resource cleanup system in a cloud infrastructure environment. You are given n resources labeled from 0 to n - 1.

The resources have hierarchical relationships represented by an array parents of length n, where parents[i] is the parent resource of resource i, or -1 if resource i has no parent. A child resource must always be deleted strictly before its parent.

In addition, you are given a list of extra_dependencies where each pair [u, v] specifies that resource u must be deleted before resource v.

Find a valid deletion order for all n resources that satisfies both the parent-child deletion constraints and all extra dependencies. If multiple valid deletion orders exist, return the lexicographically smallest one. If no valid deletion order exists due to circular dependencies, return an empty array [].

Function Signature

def get_deletion_order(n: int, parents: list[int], extra_dependencies: list[list[int]]) -> list[int]:
    pass

Input & Output Format

• Input:
  • n: an integer representing the number of resources.
  • parents: a list of integers of length n where parents[i] is the direct parent of resource i, or -1.
  • extra_dependencies: a list of lists of two integers [u, v] indicating u must precede v.
• Output: A list of integers representing the valid deletion order, or [] if impossible.

Constraints

• 1 <= n <= 5 * 10^4
• parents[i] == -1 or 0 <= parents[i] < n
• parents[i] != i
• 0 <= len(extra_dependencies) <= 10^5
• 0 <= u, v < n and u != v for each [u, v] in extra_dependencies

Examples

Example 1

Input:
n = 4
parents = [1, -1, 3, 1]
extra_dependencies = [[2, 0]]

Output:
[2, 0, 3, 1]

Explanation:
Parent constraints require:
- 0 -> 1 (0 must be deleted before 1)
- 2 -> 3 (2 must be deleted before 3)
- 3 -> 1 (3 must be deleted before 1)

Extra dependency requires:
- 2 -> 0 (2 must be deleted before 0)

Initially, only resource 2 has in-degree 0. Deleting 2 allows 0 and 3 to be deleted next. Between 0 and 3, resource 0 is smaller, so it is deleted first, followed by 3, and finally 1.

Example 2

Input:
n = 3
parents = [1, 2, 0]
extra_dependencies = []

Output:
[]

Explanation:
The parent relationships form a cycle: 0 -> 1 -> 2 -> 0. No valid deletion order exists.