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:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

2. You may assume that there are no duplicate edges in the input prerequisites.

解题要点：

在脑子里（现实中也要）构造一个directed graph，后面的prerequisite课程指向前面的课程，所以我们可以有一个hashmap/dictionary来存上完这个课程后，可以上什么课。同时也需要记录一个indegree，当前课程有几个prerequisite。把indegree为0的课程先放到queue里，每处理一个，把它后续的课程indegree减1，如果为0，加进queue。最后检测在给出的课程数量里，它们的indegrees是否都为0。

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        indegrees = [0] * numCourses
        mydict = collections.defaultdict(list)
        for i in range(len(prerequisites)):
            indegrees[prerequisites[i][0]] += 1
            mydict[prerequisites[i][1]] += prerequisites[i][0],
        
        queue = []
        for n in range(numCourses):
            if indegrees[n] == 0:
                queue.append(n)
        
        while queue:
            p = queue.pop(0)
            for e in mydict[p]:
                indegrees[e] -= 1
                if indegrees[e] == 0:
                    queue.append(e)

        for m in range(numCourses):
            if indegrees[m] != 0:
                return False
        return True