【leetcode】207. 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?

Example 1:
Input: 2, [[1,0]]

Output: true

Explanation: There are a total of 2 courses to take.

             To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: 2, [[1,0],[0,1]]

Output: false

Explanation: 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.
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.

解题思路：如果某一种输入课程无法被安排，那么一定存在至少这样一门课：通过BFS/DFS的方法从这门课开始，依次遍历需要安排在这门课后面的其他课，最终还会回到这门课，即组成了一个环。我们只有遍历所有的课，看看有没有哪门课会形成环路即可。

代码如下：

class Solution(object):

    def canFinish(self, numCourses, prerequisites):

        """

        :type numCourses: int

        :type prerequisites: List[List[int]]

        :rtype: bool

        """

        dic = {}

        for cou,pre in prerequisites:

            if pre not in dic:

                dic[pre] = [cou]

            else:

                dic[pre].append(cou)

        for i in range(numCourses):

            visit = [0] * numCourses

            queue = [i]

            start = None

            while len(queue) > 0:

                inx = queue.pop(0)

                if start == None:

                    start = inx

                elif inx == start:

                    return False

                if visit[inx] == 1:

                    continue

                visit[inx] = 1

                if inx in dic and len(dic[inx]) > 0:

                    queue += dic[inx]

        return True

巴特西

【leetcode】207. Course Schedule

最新文章

热门文章