题目描述：
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.
Hints:
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.
There are several ways to represent a graph. For example, the input prerequisites is a graph represented by a list of edges. Is this graph representation appropriate?
Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
Topological sort could also be done via BFS.
题目大意：
一共有n门需要选择的课程，标号为0到n-1。
有些课程可能会有先修课程，例如想要选择课程0，必须首先选过课程1，可以表述为配对：[0,1]
给定课程总数和一组先修课程配对，判断是否可以修完所有的课程。
例如：
2, [[1,0]]
一共有2门备选课程。要选择课程1，必须先完成课程0。因此这是可能的。
2, [[1,0],[0,1]]
一共有2门备选课程。要选择课程1，必须先完成课程0，而要修课程0，必须修完课程1。因此这是不可能的。
提示：
此问题等价于判断有向图中是否有环。如果存在环路，无法完成拓扑排序，也就不可能修完所有的课程。
表示图的方法有几种。例如，输入中的先修课程就是用一组边的方式表示图。这种图的表示方法合适吗？
通过DFS实现的拓扑排序—Cousera的一段21分钟的视频教程很好的解释了拓扑排序的基本概念。拓扑排序也可以通过BFS完成。
解题思路：
拓扑排序，如果可以完成拓扑排序，返回True，否则返回False
Python代码：
class Solution:
# @param {integer} numCourses
# @param {integer[][]} prerequisites
# @return {boolean}
def canFinish(self, numCourses, prerequisites):
degrees = [0] * numCourses
childs = [[] for x in range(numCourses)]
for pair in prerequisites:
degrees[pair[0]] += 1
childs[pair[1]].append(pair[0])
courses = set(range(numCourses))
flag = True
while flag and len(courses):
flag = False
removeList = []
for x in courses:
if degrees[x] == 0:
for child in childs[x]:
degrees[child] -= 1
removeList.append(x)
flag = True
for x in removeList:
courses.remove(x)
return len(courses) == 0
本文链接：http://bookshadow.com/weblog/2015/05/07/leetcode-course-schedule/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
