Course Schedule
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses? Tags: Graph
Try It!
Discussion
Video
Solution
import collections
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = collections.defaultdict(set)
for x, y in prerequisites:
graph[x].add(y)
visited = [0 for i in range(numCourses)]
for node in range(numCourses):
if not self.dfs(node, graph, visited):
return False
return True
def dfs(self, node, graph, visited):
if visited[node] == -1:
return False
if visited[node] == 1:
return True
visited[node] = -1
for subnode in graph[node]:
if not self.dfs(subnode, graph, visited):
return False
visited[node] = 1
return True