Leetcode** 207. Course Schedule

Description: There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Link: 207. Course Schedule

Examples:

Example 1:
Input: numCourses = 2, prerequisites = [[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: numCourses = 2, prerequisites = [[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.

思路: 第一步就是知道每门课的先修课列表，如果每门课都能顺利修成，就返回True,否则就是False。什么情况这门课可以修成？什么情况不能，例子2已经给出了不能的实例，就是正在修课程A，课程A需要先完成课程B,课程B需要修课程A,这样就冲突了。落实到DFS上，我们需要借助一个状态表，记录每个课程的状态，初始状态用0表示，修完了用1表示，正在修这门课，用2表示。定义dfs()函数的功能是，课程a是否能顺利修完，进入这个函数，a的状态是正在修，然后查看a的先修课，如果所有先修课可以顺利，则a的状态是修完，同时返回True,如果在遍历先修课时，再次遍历到a,如果a的状态是1，修完，则返回True,如果是正在修，说明冲突了，返回False.

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        self.pre = collections.defaultdict(list)
        for p in prerequisites:
            self.pre[p[0]].append(p[1])
        # 0 unvisit, 1 visited and 2 visiting
        self.visited = [0] * numCourses
        for i in range(numCourses):
            if not self.dfs(i):
                return False
        return True
    
    # dfs represent, can finish course a? if yes, return True otherwise False
    def dfs(self, a):
        if self.visited[a] == 1: return True
        if self.visited[a] == 2: return False
        self.visited[a] = 2
        for b in self.pre[a]:
            if not self.dfs(b): return False
        self.visited[a] = 1
        return True

日期: 2021-04-20 天气突然就变暖了