题目描述：
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, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
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 the correct course order is [0,1]
4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
Hints:
This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
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。因此正确的课程顺序是[0,1]。
4, [[1,0],[2,0],[3,1],[3,2]]
一共有4门备选课程。要选择课程3，必须先完成课程1和2。而课程1和2都需要先修完课程0才能选。因此一种正确的课程顺序是[0,1,2,3]。另一个正确的顺序是[0,2,1,3]。
注意：
输入的先修课程是以一组边，而非邻接矩阵形式表示的图。点此了解更多关于图表示方法的内容
提示：
此问题等价于寻找有向图的拓扑顺序。如果存在环路，不存在拓扑顺序，也就不可能修完所有的课程。
通过DFS实现的拓扑排序—Cousera的一段21分钟的视频教程很好的解释了拓扑排序的基本概念。
拓扑排序也可以通过BFS完成。
解题思路：
拓扑排序
Python代码：
class Solution:
# @param {integer} numCourses
# @param {integer[][]} prerequisites
# @return {integer[]}
def findOrder(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
ans = []
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:
ans.append(x)
courses.remove(x)
return [[], ans][len(courses) == 0]
本文链接：http://bookshadow.com/weblog/2015/05/14/leetcode-course-schedule-ii/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
