[LeetCode]Course Schedule

题目描述:

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, is it possible for you to finish all courses?

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 it is possible.

2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Hints:

This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.

There are several ways to represent a graph. For example, the input prerequisites is a graph represented by a list of edges. Is this graph representation appropriate?

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。因此这是可能的。

2, [[1,0],[0,1]]

一共有2门备选课程。要选择课程1,必须先完成课程0,而要修课程0,必须修完课程1。因此这是不可能的。

提示:

此问题等价于判断有向图中是否有环。如果存在环路,无法完成拓扑排序,也就不可能修完所有的课程。

表示图的方法有几种。例如,输入中的先修课程就是用一组边的方式表示图。这种图的表示方法合适吗?

通过DFS实现的拓扑排序—Cousera的一段21分钟的视频教程很好的解释了拓扑排序的基本概念。拓扑排序也可以通过BFS完成。

解题思路:

拓扑排序,如果可以完成拓扑排序,返回True,否则返回False

Python代码:

class Solution:
    # @param {integer} numCourses
    # @param {integer[][]} prerequisites
    # @return {boolean}
    def canFinish(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
        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:
                courses.remove(x)
        return len(courses) == 0

 

本文链接:http://bookshadow.com/weblog/2015/05/07/leetcode-course-schedule/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码