Topological Sort And Cycle Detection

What's being tested

Demonstrates modeling dependencies as a Directed Acyclic Graph (DAG), producing a valid topological sort, and cycle detection to report infeasible orderings. Interviewers probe correct graph representation, algorithm choice, and linear-time implementation with robust edge-case handling.

Patterns & templates

• Kahn's algorithm — maintain in-degree[], push zero-degree nodes into a deque, pop/process, decrement neighbors; runs in O(V+E) time.

• DFS postorder — run DFS, push node after visiting neighbors, reverse postorder yields topo; use recursion or explicit stack.

• Three-state visit — 0/1/2 (unvisited/visiting/visited) for back-edge cycle detection inside DFS.

• Adjacency list — store edges as lists/maps for O(V+E) iteration; avoid adjacency matrix unless V is tiny.

• Handle duplicates/self-loops — ignore duplicate edges when counting in-degree, and treat self-loop as immediate cycle.

• Disconnected components — initialize processing for all nodes (iterate all vertices) to include isolated nodes in ordering.

• Return semantics — when topo length < V, report cycle; otherwise return any valid ordering (multiple solutions acceptable).

Common pitfalls

Pitfall: Forgetting to iterate all nodes — only starting from given prerequisites can miss isolated vertices and produce incomplete orders.

Pitfall: Using recursion without guarding recursion depth — large graphs (V ~ 10^5) can overflow call stack; use iterative DFS or increase stack safely.

Pitfall: Counting duplicate edges twice — inflates in-degree and blocks nodes incorrectly; dedupe or tolerate duplicates in input parsing.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.