Return valid task order from prerequisites

You are given N tasks labeled 0..N-1 and a list of directed dependency pairs [(a,b), ...] meaning task a must be done before task b.

1. Return one valid execution order of all tasks that satisfies all dependencies.
2. If it is impossible (the graph has a cycle), return an empty list.

Follow-ups that may be asked:

• If multiple valid orders exist, return the lexicographically smallest order.
• Return all valid topological orders (if feasible for the input size).
• State the time and space complexity of your approach.

Constraints can be assumed typical for interview settings (e.g., up to 1e5 nodes/edges for part 1; much smaller for “all orders”).

Part 1: Return one valid execution order of all tasks

You are given n tasks labeled 0 to n-1 and a list of dependency pairs (a, b), meaning task a must be completed before task b. For this problem, you may assume the dependency graph is acyclic. Return any valid execution order that includes every task exactly once and satisfies all dependencies. If n is 0, return an empty list.

Constraints

• 0 <= n <= 100000
• 0 <= len(dependencies) <= 200000
• 0 <= a, b < n for every dependency (a, b)
• All dependency pairs are distinct
• The dependency graph is guaranteed to be acyclic for this part

Examples

Example 1

Input: (4, [(0, 1), (1, 2), (2, 3)])
Output: [0, 1, 2, 3]

Explanation: There is only one valid order because each task depends on the previous one.

Example 2

Input: (4, [(0, 2), (1, 2), (2, 3)])
Output: [0, 1, 2, 3]

Explanation: Tasks 0 and 1 can swap places, but both must appear before 2, and 2 must appear before 3. This is one valid answer.

Hints

1. Count how many prerequisites each task has.
2. Start with every task whose prerequisite count is 0, and remove tasks layer by layer.

Part 2: Return an empty list if the dependency graph contains a cycle

You are given n tasks labeled 0 to n-1 and a list of dependency pairs (a, b), meaning task a must be completed before task b. Return one valid execution order of all tasks if such an order exists. If the dependency graph contains a cycle, it is impossible to finish every task, so return an empty list.

Constraints

• 0 <= n <= 100000
• 0 <= len(dependencies) <= 200000
• 0 <= a, b < n for every dependency (a, b)
• All dependency pairs are distinct

Examples

Example 1

Input: (3, [(0, 1), (1, 2)])
Output: [0, 1, 2]

Explanation: This graph is acyclic, so a full ordering exists.

Example 2

Input: (3, [(0, 1), (1, 2), (2, 0)])
Output: []

Explanation: The dependencies form a cycle, so no valid ordering exists.

Hints

1. A topological ordering exists only if you can repeatedly remove a task with indegree 0.
2. After processing, compare how many tasks you placed in the order versus n.

Part 3: Return the lexicographically smallest valid execution order

You are given n tasks labeled 0 to n-1 and a list of dependency pairs (a, b), meaning task a must be completed before task b. Return the lexicographically smallest valid execution order among all possible topological orders. If the graph contains a cycle, return an empty list.

Constraints

• 0 <= n <= 100000
• 0 <= len(dependencies) <= 200000
• 0 <= a, b < n for every dependency (a, b)
• All dependency pairs are distinct

Examples

Example 1

Input: (4, [(0, 2), (1, 2)])
Output: [0, 1, 2, 3]

Explanation: Initially tasks 0, 1, and 3 are available. Choosing the smallest available task each time gives the lexicographically smallest order.

Example 2

Input: (6, [(2, 3), (1, 3), (0, 4)])
Output: [0, 1, 2, 3, 4, 5]

Explanation: This is the smallest order that respects all three dependencies.

Hints

1. When several tasks are ready at the same time, always choose the smallest label first.
2. A min-heap is a good way to repeatedly extract the smallest available task.

Part 4: Return all valid topological orders

You are given n tasks labeled 0 to n-1 and a list of dependency pairs (a, b), meaning task a must be completed before task b. Return all valid execution orders of the tasks. Because the number of valid orders can be exponential, assume n is small. Return the list of orders in lexicographic order. If the graph contains a cycle, return an empty list. If n is 0, return [[]], since there is exactly one ordering of zero tasks.

Constraints

• 0 <= n <= 10
• 0 <= len(dependencies) <= n * (n - 1) / 2
• 0 <= a, b < n for every dependency (a, b)
• All dependency pairs are distinct

Examples

Example 1

Input: (3, [(0, 2), (1, 2)])
Output: [[0, 1, 2], [1, 0, 2]]

Explanation: Task 2 must be last. Tasks 0 and 1 can appear in either order.

Example 2

Input: (3, [])
Output: [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

Explanation: With no dependencies, every permutation is valid.

Hints

1. Use backtracking: at each step, try every currently available task with indegree 0.
2. After exploring one choice, undo the indegree updates before trying the next choice.