Course Schedule
There are numCourses courses and pairs [a, b] meaning course b must be taken before course a. Decide whether it's possible to finish every course.
A way to picture it
Courses are dominoes. You can only push over a domino once every domino leaning on it has fallen. Start with the ones nothing leans on. If some dominoes never fall, they're propping each other up in a circle.
How to approach it
Kahn's algorithm: count each course's unmet prerequisites (in-degree). Repeatedly take a course with none, and remove its outgoing arrows. If every course gets taken, there's no cycle.
Example
Input: {"numCourses":2,"prerequisites":[[1,0]]}. Output: true.
Complexity: O(V + E) time and O(V + E) space. Every course and every prerequisite arrow is handled once.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.