There are numbered courses, and some courses require others first. A pair 1 0 means you must take course 0 before course 1. Decide whether it is possible to finish all courses.
DSA Animator › DSA Revision › Graph › Course Schedule
Remember: a schedule exists exactly when the graph has no cycle. Kahn’s algorithm takes nodes with in degree 0, one by one. The video solves Course Schedule (LeetCode 207, Medium) with the Topological Sort pattern from the Graph topic, and you can replay every step in the interactive Course Schedule animation.
There are numbered courses, and some courses require others first. A pair 1 0 means you must take course 0 before course 1. Decide whether it is possible to finish all courses.
For 4 courses with pairs 1 0, 2 0, 3 1 and 3 2, the answer is true. With only the pairs 1 0 and 0 1, each course waits for the other, so the answer is false.
Trying every order of the courses is n factorial, which is hopeless. The real question is whether the prerequisite graph has a cycle.
Draw an arrow from each prerequisite to the course that needs it. For every course, count its in degree, which is how many prerequisites it still waits for. Courses with in degree 0 can be taken right now, so put them in a queue. Taking a course removes its outgoing arrows, which lowers the in degree of the courses after it. If every course is eventually taken, there is no cycle.
The in degrees are 0 for course 0, 1 for courses 1 and 2, and 2 for course 3. Only course 0 starts in the queue. Take course 0, and courses 1 and 2 drop to in degree 0, so they join the queue. Take course 1, and course 3 drops to 1. Take course 2, and course 3 drops to 0, so it joins the queue. Take course 3, and all four courses are taken, so the answer is true.
In code, build the adjacency list and the in degree array from the pairs. Add every course with in degree 0 to a queue. Poll a course, count it, and decrease the in degree of each neighbour, adding those that reach 0. Return whether the count equals the number of courses. It's O of courses plus pairs, which is Kahn's algorithm.
Remember: a schedule exists exactly when the graph has no cycle. Kahn’s algorithm takes nodes with in degree 0, one by one.