Medium · Topological Sort
Understand → Visualise → Practice.
Prerequisites form a directed graph: an edge from A to B means A must come before B. A valid order exists only if the graph has no cycle.
Repeatedly take a course with no remaining prerequisites, and reduce the count for every course that depends on it. If you get stuck before taking all of them, there is a cycle.
in-degree of each course.
Those with in-degree 0.
Decrease neighbours; queue any that reach 0.
O(V + E) time and space, for V courses and E prerequisite pairs.
A pair [a, b] means b comes before a. Getting the edge direction backwards still finds cycles, but gives the wrong order.
Read the full guides first: Binary Trees and Traversals, Binary Search Trees, Graphs, BFS and DFS, Weighted Graphs, Dijkstra and Union–Find.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.