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