Topological Sort with Cyclic Dependency Handling

Problem Given a directed graph of dependencies, produce a topological ordering of its nodes, and detect the case where a cyclic dependency makes no valid ordering possible.

Input / Output

• Input: a directed graph as an adjacency list, an edge u -> v meaning u must come before v.
• Output: a valid topological order of all nodes, or an indication that the graph contains a cycle.

Constraints

• Nodes and edges sized for an O(V+E) solution.
• The graph may be disconnected — every node must still appear in the output.
• The ordering is generally not unique; any valid one is acceptable.

Example

• Edges A -> B, A -> C, B -> D, C -> D → valid orders include A, B, C, D and A, C, B, D.
• Cyclic case: A -> B, B -> C, C -> A → no valid ordering; report the cycle rather than emit a partial order silently.