MediumLeetCode #207Graphs

Course Schedule

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.

Constraints

1 <= numCourses <= 2000, 0 <= prerequisites.length <= 5000

Examples

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

Output: true

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

Output: false

Solution

Approach

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

Complexity

Time:O(V + E)

Space:O(V + E)

Hints

1.Model as directed graph
2.Can you finish if there is a cycle?
3.Detect cycle using DFS with visited states

Asked at

Google