mediumCodingConceptMidSenior
You are given a set of tasks and their prerequisites. Produce a valid execution order, or report that none exists.
Topological sort produces an order only for a directed acyclic graph. Kahn's algorithm removes zero-in-degree nodes and detects a cycle when fewer than all nodes are emitted; DFS detects a cycle with a back edge into the active stack. Use this GRAPHS answer to show the decision, trade-off, and evidence rather than a memorised definition.
6 min readUpdated 2026-08-15
Answer
Short answer
Topological sort orders tasks only when the prerequisite graph has no directed cycle. Use Kahn's algorithm by repeatedly emitting zero-in-degree nodes; if nodes remain, a cycle blocked the order. A DFS version pushes nodes after descendants and treats an edge to the active stack as the cycle signal.
Was this answer helpful?
Likely follow-ups
- Return the lexicographically smallest valid order. What does that cost you?
- Report the actual cycle, not just its existence.
- Why does undirected cycle detection need a different rule from the directed case?
- Tasks now have durations and can run in parallel. How do you find the earliest finish time?
Related questions
- Find the cheapest flight from one city to another using at most K stops. Why does plain Dijkstra give the wrong answer?mediumAlso on graphs5 min
- How do you decide between BFS and DFS - and how do you recognise a graph problem that nobody described as a graph?mediumAlso on graphs4 min
- Find the cheapest route between two nodes in a weighted directed graph. Then tell me what breaks if one edge has a negative weight.mediumAlso on graphs5 min
- Count the islands in a grid of land and water. Then land is added one cell at a time, and you report the island count after every addition.mediumAlso on graphs5 min