Skip to main content

Course Schedule

Question​

Given a list of courses and their prerequisites, how can a valid course schedule be constructed such that all prerequisites are satisfied?

Example 1
Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]

Solution​

all//Course Schedule.py


def courseSchedule(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    visited = [0 for _ in range(numCourses)]

    for x, y in prerequisites:
        graph[x].append(y)

    def dfs(i):
        if visited[i] == -1:
            return False
        if visited[i] == 1:
            return True
        visited[i] = -1

        for j in graph[i]:
            if not dfs(j):
                return False

        visited[i] = 1
        return True

    for i in range(numCourses):
        if not dfs(i):
            return False

    return True