There are a total of numCourses courses you have to take. Some courses may have prerequisites. Given the total number of courses and a list of prerequisite pairs, determine if it is possible to finish all courses.
1 <= numCourses <= 2000, 0 <= prerequisites.length <= 5000
Detect cycle in directed graph. Use DFS with 3 states (unvisited, visiting, visited) or BFS with indegree (Kahn's algorithm).
def canFinish(numCourses, prerequisites):
graph = [[] for _ in range(numCourses)]
for course, prereq in prerequisites:
graph[prereq].append(course)
state = [0] * numCourses # 0=unvisited, 1=visiting, 2=visited
def dfs(node):
if state[node] == 1:
return False # cycle
if state[node] == 2:
return True
state[node] = 1
for neighbor in graph[node]:
if not dfs(neighbor):
return False
state[node] = 2
return True
for i in range(numCourses):
if not dfs(i):
return False
return True