207.course_schedule.md

207. Course Schedule

中等

https://leetcode-cn.com/problems/course-schedule/

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All the pairs prerequisites[i] are unique.

相关企业

• 亚马逊 Amazon|29
• 微软 Microsoft|13
• Facebook|10
• 谷歌 Google|4
• 字节跳动|4

相关标签

• Depth-First Search
• Breadth-First Search
• Graph
• Topological Sort

相似题目

• Course Schedule II 中等
• Graph Valid Tree 中等
• Minimum Height Trees 中等
• Course Schedule III 困难

隐藏提示1

• This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.

隐藏提示2

• Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.

隐藏提示3

• Topological sort could also be done via BFS.

O(V + E)

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # build directed graph and count indegree
        course2indegreeMap, course2neighborsGraph = self.buildGraphAndCourse2IndegreeMap(numCourses, prerequisites)

        # bfs
        startcourses = [course for course in course2indegreeMap if course2indegreeMap[course] == 0]
        queue = collections.deque(startcourses)
        topoorder = []
        while queue:
            curr_course = queue.popleft()
            topoorder.append(curr_course)
            for nextcourse in course2neighborsGraph[curr_course]:
                course2indegreeMap[nextcourse] -= 1
                if course2indegreeMap[nextcourse] == 0:
                    queue.append(nextcourse)
        # if one topological order contains all courses then true
        if len(topoorder) == numCourses: 
            return True
        return False
        

    def buildGraphAndCourse2IndegreeMap(self, numCourses, prerequisites):
        # add all courses and initalize its indegree as 0
        course2indegreeMap = {cour: 0 for cour in range(numCourses)}
        # course and its next level courses
        course2neighborsGraph = {cour: [] for cour in range(numCourses)}
        # record indegree and record next level courses
        for prereq in prerequisites:
            course2neighborsGraph[prereq[1]].append(prereq[0]) 
            course2indegreeMap[prereq[0]] += 1
        return course2indegreeMap, course2neighborsGraph