There are numCourses courses. prerequisites[i]=[a,b] means you must take b before a. Return true if you can finish all courses (no cycle), else false.
n=2, prereqs=[[1,0]]trueState 1 = "in current DFS path". If we recurse to a node with state 1, we've found a back edge (cycle). State 2 = fully processed, safe to skip.
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.
A schedule exists exactly when the graph has no cycle. Kahn’s algorithm takes nodes with in degree 0, one by one.
Run the animation above on your own input, or watch the 2:03 video explanation of Course Schedule with a dry run and Java code.