207. 课程表 [medium]

https://leetcode-cn.com/problems/course-schedule/

你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。

在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]

给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]] 
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例 2:

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

提示：

输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
1 <= numCourses <= 10^5

通过次数43,411 | 提交次数84,060

Third Try

2020-08-04

leetcode的每日一题打卡，又是做过的，不过细节竟然都忘得差不多了，还是花费了很长时间。

这题本质上是判断有向图中是否存在环。

一开始还只是用graph循环遍历，看是否有没被遍历到的，后来才发现还需要考虑内循环。已经忘记之前的技巧了，想来想去还是用dfs回溯法进行分别判断，结果一看跟first try第一次尝试的解法竟然一样。看来虽然second try更是正统，但是一般很难想到。

second try里面像拨洋葱一样，露头的才处理，两次合理利用了indegree.

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        """
        循环起来，就悲剧了
        3
        [[0,2],[1,2],[2,0]]
        """

        if numCourses == 1 or len(prerequisites) == 0:
            return True 

        indegree = [0] * numCourses
        graph = collections.defaultdict(list)
        for pre, curr in prerequisites:
            indegree[curr] += 1 
            graph[pre].append(curr)

        # innode简单验证一波，但考虑的不是多个innode，而是没有innode
        innode = []
        for i in range(numCourses):
            if indegree[i] == 0:
                innode.append(i)
        if len(innode) == 0: # 防止循环为0没有开头
            return False 
        # print('innode', innode)

        def dfs(node, visited, total_visited):
            for n in graph[node]:
                if n in visited:
                    return False 
                total_visited.add(n)
                visited.add(n)
                if not dfs(n, visited, total_visited):
                    return False # return都被遗忘了
                visited.remove(n)
            return True 
        
        total_visited = set(innode)
        for n in innode:
            if not dfs(n, set([n]), total_visited):
                return False 

        # print("total visited", total_visited)
        if len(total_visited) != numCourses:
            return False 
        return True 

        # 还是得遍历循环一波
        # visited = set(innode)
        # queue = innode
        # while len(queue):
        #     node = queue.pop(0)
        #     for n in graph[node]:
        #         if n in visited:
        #             continue 
        #         visited.add(n)
        #         queue.append(n)

        # if len(visited) !=  numCourses:
        #     return False 
        # print(visited)
        # return True 

执行用时：68 ms, 在所有 Python3 提交中击败了23.43%的用户
内存消耗：16.6 MB, 在所有 Python3 提交中击败了10.81%的用户

Second Try

2020-06-29

BFS入度表版本，应该是比较标准的有向无环图处理方法，看题解了解到的。不过我的写法跟题解不太一样，还是更倾向使用defaultdict而非列表，但也导致引入了一个容易出现的bug:如果某个课程是独立的并没有在prerequisites中，就会被忽略过去，解决办法是判断一遍是否已经统计了所有的course.

一点点做题，成就感还是比较强。看书的时候还没练习，现在对图还是没什么把握。

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        # 换一个标准版本搞拓扑排序

        nodes = set()
        graph = defaultdict(set)
        indegree = defaultdict(int)  # 不是标准的indegree，别人都是用列表
        for curr, prereq in prerequisites:
            graph[prereq].add(curr)
            indegree[curr] += 1
            nodes.update(set([curr, prereq]))  # 其实如果某个course并没有先后关系，也就不会被遍历到
        if len(nodes) != numCourses:  # 那些因为独立而没有被遍历到的，可以直接忽略掉, critical point!
            numCourses = len(nodes)
        incomes = nodes - set(indegree.keys())  # only root prereq will be included
        queue = list(incomes)
        while queue:
            node = queue.pop(0)
            numCourses -= 1  # every course in the graph should be pop once
            for n in graph[node]:  # if node has no successor, graph[node] is empty
                indegree[n] -= 1
                if indegree[n] == 0:
                    queue.append(n)
        return numCourses == 0

执行用时：60 ms, 在所有 Python 提交中击败了23.27%的用户
内存消耗：14.3 MB, 在所有 Python 提交中击败了33.33%的用户

First Try

2020-06-28

DFS版本，一开始看到这题以为不会做，后来尝试构建了一下图，再画图发现可以用DFS和visited来做，叠加上回溯法，竟然也就搞定了。不错不错。

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        # 本质就是在有向图里找环

        # 这个特殊情况还真是特别，没有先觉条件，那么所有课都可以随便选
        if not prerequisites:
            return True

        # 构建一波有向图
        graph = collections.defaultdict(set)
        c_all = set()
        c_to = set()
        for (curr, prereq) in prerequisites:
            graph[prereq].add(curr)
            c_all.update(set([curr, prereq]))
            c_to.add(curr)

        
        # 感觉需要找到一波作为起点才行
        # 但是这个写法有个缺陷，如果一边是正常的图，另一边是一个环，那个环就不会被触碰到了
        # 需要在遍历过程中对所有点进行判断，确定真的找到了所有的点才行
        c_start = c_all.difference(c_to)
        if not c_start:
            return False

        # print(c_start)

        # 本来觉得每次都得开启新得set来进行新得判断，写着写着才想到可以用回溯法
        def check_circulate(node, visited, all_visited):
            all_visited.add(node)
            for to in graph[node]:
                if to in visited:
                    return False
                # bug写法，set.add之后并不会返回新的set...
                # if not check_circulate(to, visited.add(to)):
                visited.add(to)
                if not check_circulate(to, visited, all_visited):
                    return False
                else:
                    visited.remove(to)
            return True

        # 对所有起点来一波深度遍历
        all_visited = set() # 判断是否能够走完所有的点
        for c in c_start:
            if not check_circulate(c, set([c]), all_visited):
                return False
        if len(all_visited.symmetric_difference(c_all)) != 0:
            return False
        return True

执行用时：52 ms, 在所有 Python 提交中击败了28.04%的用户
内存消耗：16.7 MB, 在所有 Python 提交中击败了33.33%的用户