题目

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. 不断弹出零入度队列，并且维护（删除）弹出任务的出度关系，当维护出度任务时若该任务的入度为零则加入队列，直到队列为空。

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                

LeetCode 207. Course Schedule（拓扑排序）