Course Schedule

Graph
Medium

Approach

Diagrams

Analysis

Time

Space

class Solution:
    def canFinish(self, numCourses, prereqs):
        visited = [0 for course in range(numCourses)]
        graph = self.buildGraph(numCourses, prereqs)

        for course in range(numCourses):
            isImpossible = not self.dfs(course, visited, graph)
            if isImpossible:
                return False

        return True

    def dfs(self, course, visited, graph):
        isCycle = visited[course] == -1
        isVisited = visited[course] == 1

        if isCycle:
            return False

        if isVisited:
            return True

        visited[course] = -1

        for prereq in graph[course]:
            isImpossible = not self.dfs(prereq, visited, graph)
            if isImpossible:
                return False

        visited[course] = 1

        return True

    def buildGraph(self, numCourses, prereqs):
        graph = [[] for course in range(numCourses)]

        for course, prereq in prereqs:
            graph[course].append(prereq)

        return graph

Learn

#Depth-First Search

Videos