Lintcode 615. Course Schedule

题目求先修课程有没有冲突，算法是用bfs， 拓扑排序

拓扑排序：找到有向图中，从头到尾的一种排序，所以中间没有环路。

算法：首先需要邻接矩阵和计算每个课程的入度。将入度为0的排入队列中，对队列中的点进行遍历，将队列中点的邻居的入度减1，如果入度减为0了，将邻居也排入队列中，直到队列为空。

在这道题中，可以设置一个count来计算是否把所有的课程都遍历一遍，如果有闭环，闭环的接口始终入度不可能为0，就无法被放入队列中，所以count就会不等于总的课程数。

python代码：

```

from collections import deque

class Solution:

    """

    @param: numCourses: a total of n courses

    @param: prerequisites: a list of prerequisite pairs

    @return: true if can finish all courses or false

    """

    def canFinish(self, numCourses, prerequisites):

        # write your code here

        edge = [[] for i in range(numCourses)]

        indegree = [0] * numCourses

        for i, j in prerequisites:

            edge[j].append(i)

            indegree[i] += 1

        cnt = 0

        queue = deque()

        for i in range(numCourses):

            if indegree[i] == 0:

                queue.append(i)

        while queue:

            course = queue.popleft()

            cnt += 1

            for requirecourse in edge[course]:

                indegree[requirecourse] -= 1

                if indegree[requirecourse] == 0:

                    queue.append(requirecourse)

        return cnt == numCourses

```