This is a graph question. To be a valid course schedule the graph will need to be a directed acycle graph (DAG). If a cycle is found then the course schedule is NOT valid.

DFS tranversal can be used to walk the graph and detect any cycles. The DFS algorithm is modified to keep track of the status of a vertex. The statuses are:

Not visited

Processing

Processed

Invalid Course Schedule

When traversing the graph, if a vertex is found to be in "Processing" status then a cycle has been detected.

For example, assume the following class schedule [[0, 1], [1, 0]]. Here the class schedule says:

class 0 has a prerequisite of class 1

class 1 has a prerequisite of class 0

So, there is a cycle. When traversing the graph, we will visit vertex 0, traverse to vertex 1 and then back to vertex 0. Because vertex 0 is in status "processing" a cycle is detected.

Now we are in a cycle because course 1 has a prerequisite of course 0 (which is in status "processing"). So the algorithm can stop because we now know the course schedule is invalid.

Valid Course Schedule

If the algorithm does not encounter any vertices with "processing" status, then there are not cycles and the course schedule is valid.

Example: assume the following course schedule: [[0,1], [1,2]]. This means:

Course 0 has a prerequisite of Course 1

Course 1 has a prerequisite of Course 2

Here there are no cycles. So, when following the edges from a vertex we will not encounter a vertex in "processing status". If we come across a vertex that has status "processed" then we can skip it. We have already traversed it and found it to be valid. So there is no point in processing it again.

Algorithm

from collections import defaultdictfrom typing import Listfrom enum import EnumclassStatus(Enum): NOT_VISITED =0 PROCESSING =1 PROCESSED =2classSolution:defdfs(self,start,course_graph,visited) ->bool: # We will keep track of the status of each vertex. If we come across a processed vertex then we can exit as we don't need to reprocess it
if visited[start]== Status.PROCESSED:returnTrue # If we come across a vertex that is marked as "processing" then we have encountered a cycle. We are currently processing that vertex and one of its edges led back to it! So, we can return False as it is not a valid course schedule
if visited[start]== Status.PROCESSING:returnFalse visited[start]= Status.PROCESSING # defaultdict will automatically add a key if it is not found in the dict. The if statement is here to prevent a key from being added if it does not exist
if start in course_graph:for node in course_graph[start]:ifnot self.dfs(node, course_graph, visited): # we enountered a vertex that was in processing status. So a cycle exits. Return False as the course prerequisites are not valid.
returnFalse# If we make it here then a cycle did not exist and the course prerequistes are valid. # Mark the vertex as processed so we do not prcess it again. We've determined this course has valid prerequisites.
visited[start]= Status.PROCESSEDreturnTruedefcanFinish(self,numCourses:int,prerequisites: List[List[int]]) ->bool:# create a graph where the keys are the courses and the values are the prerequisites for each course course_graph =defaultdict(list)for course, prereq in prerequisites: course_graph[course].append(prereq) visited = [Status.NOT_VISITED] * numCourses# every key needs to be traversed because the graph may be disconnectedfor key in course_graph:ifnot self.dfs(key, course_graph, visited):returnFalsereturnTrue

Kahn's Algorithm Solution

Kahn's Algorithm can also be used to detect a valid course schedule.

from collections import defaultdict, dequefrom typing import ListclassSolution:defcanFinish(self,numCourses:int,prerequisites: List[List[int]]) ->bool:# create a graph where the keys are the courses and the values are the prerequisites for each course course_graph =defaultdict(list)# this array keeps track of how many edges are incoming to a vertex (how many dependecies a course has)# because the course ids are 0 <= a, b <= numCourses, array index is course id incoming_edges = [0] * numCourses# populate the incoming_edges with the number of prerequisites for each coursefor course, prereq in prerequisites: course_graph[prereq].append(course) incoming_edges[course]+=1# initialize the queue with any courses that do NOT have any prerequisites processing_queue =deque()for course, prereq inenumerate(incoming_edges):if prereq ==0: processing_queue.append(course)# we don't need a topological ordering for this scenario. We just need to know if the schedule is valid or not# so just keep track of the number of classes processed. If it differs from the graph size then the schedule is# invalid num_classes_processed =0while processing_queue: num_classes_processed +=1 course = processing_queue.pop()for dependency in course_graph[course]: incoming_edges[dependency]-=1if incoming_edges[dependency]==0: processing_queue.append(dependency)return num_classes_processed == numCourses