【leetcode】207. Course Schedule

题目如下：

解题思路：如果某一种输入课程无法被安排，那么一定存在至少这样一门课：通过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