Course Schedule

题目

There are a total ofncourses you have to take, labeled from0ton - 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 prerequisitepairs, 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.

思路分析

这道题很明显是一道graph的题，考察点的是topological sort，可以使用BFS来实现，也可以通过DFS来实现

• BFS实现

用BFS实现topological sort的时候要把graph先present出来，在python中可以用dictionary的方式来表示，每一个vertex作为key，value就是每一个vertex的所有neighbors，这些neighbors放在一个set里面。同时呢还要把每一个vertex的indegree用dictionary表示出来，key还是vertex，value就是每一个vertex的indegree数，也就是说要在graph中有几个vertex指向了当前的vertex。直到了每一个vertex的indegree之后就可以每一次把indegree为0的vertex放在queue中一直到最后一个vertex的indegree为0。

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        graghMap = {i: set() for i in xrange(numCourses)}
        indegreeMap = {i: 0 for i in xrange(numCourses)}
        courseList = []
        for neighbor, course in prerequisites:
            graghMap[course].add(neighbor)
            indegreeMap[neighbor] = indegreeMap[neighbor] + 1
        queue = [course for course in indegreeMap if indegreeMap[course] == 0]
        while queue:
            course = queue.pop(0)
            courseList.append(course)
            for neighbor in graghMap[course]:
                indegreeMap[neighbor] -= 1
                if indegreeMap[neighbor] == 0: queue.append(neighbor)
        return len(courseList) == numCourses

• DFS实现

用DFS实现topological sort的时候可以通过任意一个没有被visited的vertex出发，所以要先建立一个visited数组，这个数组的初始值是每一个vertex都没有被visited过：

• if vertex has not been visited, then mark it as 0.
• if vertex is being visited, then mark it as -1. If we find a vertex marked as -1 in DFS, then their is a ring.
• if vertex has been visited, then mark it as 1. If a vertex was marked as 1, then no ring contains vertex or its successors.

visited数组清楚了之后，还要弄清楚topological sort之后的数组是怎样构建的，因为每一次都是最后一个vertex先被check到，所以要想得到topological sort后的数组，每一次插入到数组的head中，或者先append到最后，然后反转数组

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        graphMap = {i: set() for i in xrange(numCourses)}
        visited = [0 for i in xrange(numCourses)]
        for neighbor, course in prerequisites:
            graphMap[course].add(neighbor)
        for course in graphMap:
            if visited[course] == 0: 
                if not self.dfs(graphMap, course, visited): return False
        return True

    def dfs(self, graph, course, visited):
        if visited[course] == -1: return False
        if visited[course] == 1: return True
        visited[course] = -1
        for neighbor in graph[course]:
            if not self.dfs(graph, neighbor, visited): return False
        visited[course] = 1
        return True