Graph Theory37 sections · 1633 units
Open in Course

Course Schedule II - Core Idea

In-degree tracks readiness

In-degree tracks readiness. Each course starts with an in-degree equal to its number of prerequisites. When in-degree reaches 00, all prerequisites are complete and the course is ready to take.

You push all courses with in-degree 00 into a queue. Each time you pop a course, you "take" it and remove its outgoing edges. This decreases the in-degree of dependent courses. When a dependent course's in-degree drops to 00, it enters the queue.

If you process all nn courses, you have a valid schedule. If some courses remain with in-degree >0> 0, those courses form a cycle and the schedule is impossible.