Deploy Dependency Order
A release engineer has a list of services to deploy and a list of dependency edges ("service A must be deployed before service B"). They need a deploy order that respects all dependencies, or a clear signal that no order is possible.
Problem
You are given an integer n (number of services, numbered 0..n−1) and a list of pairs (a, b) meaning service a must be deployed strictly before service b. Return any valid topological ordering of the services. If no valid order exists (i.e., the dependency graph has a cycle), return an empty list.
Input
Integer n (1 ≤ n ≤ 10^4) and a list of m pairs (a, b) with 0 ≤ a, b < n and a ≠ b (1 ≤ m ≤ 5·10^4).
Output
A list of n integers — a valid topological order. Empty list if the graph is cyclic.
Constraints
- 1 ≤ n ≤ 10,000
- 0 ≤ m ≤ 50,000
- Edges may contain duplicates — treat them as a single edge
- Multiple valid orders may exist; any one is acceptable
Examples
Example 1
Input
n = 4, edges = [(0,1), (0,2), (1,3), (2,3)]
Output
[0, 1, 2, 3] (or [0, 2, 1, 3])
0 must precede 1 and 2; both 1 and 2 must precede 3. Both orderings honor every edge.
Example 2
Input
n = 3, edges = [(0,1), (1,2), (2,0)]
Output
[]
Cycle 0 → 1 → 2 → 0 — no valid order exists.