首页 > 其他 > 详细

207 Course Schedule

时间:2015-07-07 14:25:02      阅读:200      评论:0      收藏:0      [点我收藏+]

使用 拓扑排序, 使用刚学的defaultdict 哈哈

from collections import defaultdict
class Solution:
    # @param {integer} numCourses
    # @param {integer[][]} prerequisites
    # @return {boolean}
    def canFinish(self, numCourses, prerequisites):
        inNum = [0 for i in range(numCourses)]
        dic = defaultdict(list)
        for [u,v] in prerequisites:
            dic[u].append(v)
            inNum[v] += 1
        totalNum = 0
        while 0 in inNum:
            u = inNum.index(0)
            if u in dic:
                for v in dic[u]:
                    inNum[v] -= 1
            inNum[u] = None
            totalNum += 1
        return totalNum == numCourses

 

207 Course Schedule

原文:http://www.cnblogs.com/dapanshe/p/4626715.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!