LeetCode 207. Course Schedule（拓扑排序）

时间：2022-09-06 05:51:50

题目

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

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.

Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

解题思路

  1. 本质是一个拓扑排序的问题。
  2. 将各个任务的入度和出度计算并存储起来
  3. 将入度为零的任务放在一个队列中
  4. 不断弹出零入度队列，并且维护（删除）弹出任务的出度关系，当维护出度任务时若该任务的入度为零则加入队列，直到队列为空。

LeetCode 207. Course Schedule（拓扑排序）

class Solution(object):

    def canFinish(self, numCourses, prerequisites):

        """

        :type numCourses: int

        :type prerequisites: List[List[int]]

        :rtype: bool

        """

        # 创建入度出度空字典

        inDegree, outDegree = {x:[] for x in range(numCourses)}, {x:[] for x in range(numCourses)}

        # 存储入度出度关系

        for course, preCourse in prerequisites:

            inDegree[course].append(preCourse)

            outDegree[preCourse].append(course)

        count, emptyQueue = 0, []

        # 将入度为零的任务加入队列

        for i in range(numCourses):

            if not inDegree.get(i):

                emptyQueue.append(i)

        # 弹出任务，维护任务

        while emptyQueue:

            node = emptyQueue.pop()

            count += 1

            for j in outDegree[node]:

                inDegree[j].remove(node)

                if not inDegree.get(j):

                    emptyQueue.append(j)

        return count == numCourses

　　

　　

相关文章