Lintcode 616. Course Schedule II

同样是拓扑排序,需要注意的是防治出现闭环的情况。当出现闭环,返回空。
python 代码:

class Solution:
    """
    @param: numCourses: a total of n courses
    @param: prerequisites: a list of prerequisite pairs
    @return: the course order
    """
    def findOrder(self, numCourses, prerequisites):
        # write your code here
        from collections import deque
        edge = [[] for i in range(numCourses)]
        indegree = [0] * numCourses
        for i, j in prerequisites:
            edge[j].append(i)
            indegree[i] += 1
        res = []
        queue = deque()
        cnt = 0
        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)
        while queue:
            course = queue.popleft()
            res.append(course)
            cnt += 1
            for neighbor in edge[course]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    queue.append(neighbor)
        if cnt != numCourses:
            return []
        return res
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容