Topological Sort with Parallelized DFS

Problem Given a directed acyclic graph (DAG), produce a topological ordering of its nodes, then extend the discussion to how the traversal could be parallelised across multiple workers or threads.

Input / Output

• Input: a DAG as an adjacency list over n nodes.
• Output: a linear ordering of all nodes such that every edge u -> v places u before v. Any valid ordering is acceptable — the ordering is generally not unique.

Constraints

• Graph is guaranteed acyclic.
• Up to ~10^5 nodes and edges; the graph may be disconnected.
• Independent branches exist that could legitimately be processed concurrently.

Example

• A task dependency graph: build -> test, build -> lint, test -> deploy, lint -> deploy. Valid orders include build, test, lint, deploy and build, lint, test, deploy — test and lint are mutually independent and could run at the same time.
• Tricky case: an isolated node with no edges must still appear in the output.