Topological Sorting And Cycle Detection

What's being tested

Candidates must model dependency graphs and produce a valid Topological sort when possible, or detect a cycle that makes ordering impossible. Interviewers probe graph representation choices, algorithm selection (Kahn vs DFS), correctness, and edge-case handling like self-dependencies and disconnected nodes.

Patterns & templates

• Kahn's algorithm — build an adjacency list + in-degree array, use collections.deque, process zero in-degree nodes; time O(V+E), space O(V+E).

• DFS-based topological sort — run DFS, push nodes to output on post-order; detect back-edges with a recursion stack for cycle detection.

• Represent graph with a dict of lists or vector-of-vectors for sparse graphs; avoid O(V^2) adjacency matrices unless V is tiny.

• Handle nodes with no edges explicitly: include all vertices in the initial data structures to produce complete orderings.

• For multiple valid orders, return any valid topological ordering and document nondeterminism; use a min-heap to produce lexicographically smallest order when required.

• Detect cycles by comparing output length to V (Kahn) or by encountering a node already in the recursion stack (DFS).

• Watch recursion depth for large V (~10^5); switch to iterative DFS or increase recursion limit in languages like Python.

Common pitfalls

Pitfall: Forgetting to include isolated nodes leads to missing tasks in the result.

Pitfall: Using adjacency matrix or O(V^2) operations on V up to 10^5 causes TLE or memory blowups.

Pitfall: Not handling self-loops correctly — they are cycles and should make ordering impossible.