Return a Valid Dependency Order for Named Tasks

Problem Statement

You are building an execution engine for an automated build pipeline. You are given a list of task dependencies dependencies, where each element is a pair (u, v) indicating that task u must be completed before task v can begin.

Write a function to return the execution order of all tasks such that every dependency requirement is satisfied. Your solution must satisfy the following requirements:

1. Completeness: Every unique task appearing in dependencies (either as prerequisite u or dependent v) must be included in the output.
2. Deduplication: Duplicate dependency pairs in the input must be handled correctly without affecting in-degree calculations.
3. Deterministic Order: If multiple tasks are eligible to run at the same time (i.e., all their prerequisites have finished), pick the task with the lexicographically smallest name first.
4. Cycle Detection: If a circular dependency exists such that not all tasks can be completed, return an empty list [].

Function Signature

def find_task_order(dependencies: list[tuple[str, str]]) -> list[str]:
    pass

Input & Output Format

• Input: dependencies, a list of tuples (u, v) where u and v are non-empty strings representing task names.
• Output: A list of strings representing the ordered task sequence, or [] if a cycle prevents scheduling all tasks.

Constraints

• 0 <= len(dependencies) <= 10^5
• Task names consist of lowercase and uppercase English letters, digits, and underscores.
• 1 <= len(task_name) <= 50

Examples

Example 1

Input: dependencies = [
    ("build", "test"),
    ("lint", "test"),
    ("fetch", "build"),
    ("setup", "lint")
]
Output: ["fetch", "setup", "build", "lint", "test"]

Explanation: Tasks "fetch" and "setup" have no prerequisites. "fetch" < "setup", so "fetch" runs first, unblocking "build". Next, among available tasks {"build", "setup"}, "build" comes before "setup". Following this logic with lexicographical tie-breaking yields ["fetch", "setup", "build", "lint", "test"].

Example 2

Input: dependencies = [
    ("A", "B"),
    ("B", "C"),
    ("C", "A")
]
Output: []

Explanation: There is a cycle A -> B -> C -> A. No task can ever have zero prerequisites satisfied, so return [].

Edge Cases

• Empty input list dependencies = [] should return [].
• Redundant duplicate edges like [("A", "B"), ("A", "B")] should not artificially inflate B's in-degree.
• Disconnected graph components should all be scheduled, ordered by lexicographical priority among currently available roots.