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

Topological sort using in-degree. If all courses processed, no cycle exists.

Implementation

def canFinish(numCourses, prerequisites):
    from collections import defaultdict, deque
    
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    count = 0
    
    while queue:
        course = queue.popleft()
        count += 1
        for next_course in graph[course]:
            in_degree[next_course] -= 1
            if in_degree[next_course] == 0:
                queue.append(next_course)
    
    return count == numCourses

Complexity Analysis

Time Complexity

O(V + E)

Space Complexity

O(V + E)

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