[leetcode/lintcode 題解] 阿裡面試真題詳解：課程表 II

描述

你需要去上n門九章的課才能獲得offer，這些課被标号為 0 到 n-1 。 有一些課程需要“前置課程”，比如如果你要上課程0，你需要先學課程1，我們用一個比對來表示他們： [0,1]

給你課程的總數量和一些前置課程的需求，傳回你為了學完所有課程所安排的學習順序。

可能會有多個正确的順序，你隻要傳回一種就可以了。如果不可能完成所有課程，傳回一個空數組。

線上評測位址：

領扣題庫官網

樣例1
輸入: n = 2, prerequisites = [[1,0]] 
輸出: [0,1]           

樣例2
輸入: n = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] 
輸出: [0,1,2,3] or [0,2,1,3]           

解題思路

拓撲排序，輸出任意一種拓撲序列。

源代碼

class Solution:
    # @param {int} numCourses a total of n courses
    # @param {int[][]} prerequisites a list of prerequisite pairs
    # @return {int[]} the course order
    def findOrder(self, numCourses, prerequisites):
        # Write your code here
        edges = {i: [] for i in xrange(numCourses)}
        degrees = [0 for i in xrange(numCourses)] 
        for i, j in prerequisites:
            edges[j].append(i)
            degrees[i] += 1
        import Queue
        queue = Queue.Queue(maxsize = numCourses)
        
        for i in xrange(numCourses):
            if degrees[i] == 0:
                queue.put(i)

        order = []
        while not queue.empty():
            node = queue.get()
            order.append(node)

            for x in edges[node]:
                degrees[x] -= 1
                if degrees[x] == 0:
                    queue.put(x)

        if len(order) == numCourses:
            return order
        return []           

更多題解參考：

九章官網solution