Delete entities in a dependency-safe order

Entities have parent-child relationships, and a parent can only be deleted after all of its children. On top of that, some extra rules say that one entity must be deleted before another. Model this as a graph and return an order that deletes every entity without breaking a rule. Among valid orders, return the lexicographically smallest. If the rules contradict each other, report that no order exists.

Interface

Unless you agree on a different interface with the interviewer, assume:

• deletion_order(n: int, parent: list[int], before: list[tuple[int, int]]) -> list[int] — entities are 0..n-1; parent[i] is the parent of i, or -1. Each pair (x, y) in before means x must be deleted before y. Return the smallest valid order, or [] when a cycle makes it impossible.

Example

parent = [-1, 0, 0, 1]          # 0 is the root; 1 and 2 are its children; 3 is under 1
deletion_order(4, parent, [])          ->  [2, 3, 1, 0]
deletion_order(4, parent, [(3, 2)])    ->  [3, 1, 2, 0]
deletion_order(4, parent, [(0, 3)])    ->  []    # 0 before 3, but 3 before 1 before 0

Constraints

• Up to 10^5 entities and extra rules.
• The parent links alone form a forest; the extra rules may create cycles.

Clarifying questions

• Does a parent need all of its descendants deleted first, or only its direct children? (With child-to-parent edges, these are the same.)
• What do the extra pairs mean exactly, and can they repeat?
• Is a cycle reported as an empty list, an error, or the entities involved?
• Is "lexicographically smallest" by entity id?

What a strong answer covers

• Edges child -> parent and x -> y, then Kahn's algorithm with a min-heap in place of a queue, which yields the lexicographically smallest topological order. O((n + m) log n).
• Cycle detection: fewer than n entities come out of the heap.
• Why a plain DFS post-order does not give the smallest order.
• Tests: a forest of several roots, duplicate rules, a rule that agrees with the tree, a cycle.

Follow-ups

• Report the entities on one cycle so a user can fix the rules.
• Deletions run in parallel rounds; everything with no remaining blockers goes at once. How many rounds are needed?
• Entities and rules are added while deletions are being planned.