210.md

Course Schedule II

题目:

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.

Example 1:

Input: 2, [[1,0]] 
Output: [0,1]
Explanation: 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] .
Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: 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. You may assume that there are no duplicate edges in the input prerequisites.

思路：

解法1：使用一个二维数组记录课程的依赖关系，比如Input: 4, [[1,0],[2,0],[3,1],[3,2]]

使用这样一个图表示依赖关系： [ [] [0] [0] [1,2] ] 使用两个数组记录completed，和uncomplete，uncomplete初始化为[0....numCourses-1]

遍历uncomplte，如果graph[i]的长度为0，表示可以修这门课程了，将该课程加入到completed。

然后将uncomplete中的改课程删除，在将graph中包含该课程依赖关系删除。

循环直到complete的长度==numCourses。

如果在遍历过程中，complete的长度没有加长，那么表示含有内环，返回空列表[]。

代码：

解法1

class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        graph = [[] for row in range(numCourses)]
        for prerequisite in prerequisites:
            graph[prerequisite[0]].append(prerequisite[1])
        completed = []
        uncomplete = [ c for c in range(numCourses)]
        last_len = 0
        while len(completed) != numCourses:
            for c in uncomplete:
                if len(graph[c]) == 0:
                    completed.append(c)
            if len(completed)==last_len:
                return []
            for i in range(last_len, len(completed)):
                uncomplete.remove(completed[i])
            for c in uncomplete:
                for i in range(last_len,len(completed)):
                    if completed[i] in graph[c]:
                        graph[c].remove(completed[i])
            last_len = len(completed)
        return completed