210. Course Schedule II

Loading...LeetCode

BFS

第一反应是把不同 course 当作 tree 上的 node，这样就可以 BFS/DFS 遍历到底，没能遍历到的就是上不了的课。为了处理 node 间的关系，需要双向 mapping 一下 prerequisites，需要注意的地方是有些课有超过一个 prerequisite，这样的话需要等它的所有 prerequisites 都访问过了才能访问它。

一开始用了 subset 来判断是不是所有 prerequisite 都已经在 taken 了，后来意识到可以直接修改 prerequisite 的 mapping，每上一个课就把这个课从 require 它的课程 prerequisites 里去掉，效率快很多。

Edge Tracking

taken里上过的课不会再丢掉，而且任何可以上的课（BFS能访问的node）都会加入taken，所以我们可以直接维护taken来取代 queue。

Indegree

用indegree 来替代 prerequisite mapping，这样不需要记录具体的课程，只要每上一门 pre 就在 indegree 减一，等 indegree 到 0 的时候就代表所有需要的 pre 都上过了。

这个方法应该是最快的，但很奇怪 leetcode 里提交它比 mapping 还慢。

BFS

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        req, fol = collections.defaultdict(set), collections.defaultdict(set)
        for (a, b) in prerequisites:
            fol[b].add(a)
            req[a].add(b)
        
        taken = []
        # 不需要任何 prerequisite 的课程
        for i in range(numCourses):
            if i not in req:
                taken.append(i)
        
        q = collections.deque(taken)
        while q:
            curr = q.popleft()
            for c in fol[curr]:
                # 该课程的所有 prerequisite 都访问过了，才可以访问它
                if req[c].issubset(set(taken)) and c not in taken:
                    taken.append(c)
                    q.append(c)
                    
        return taken if len(taken) == numCourses else []

Edge Tracking

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        req, fol = collections.defaultdict(set), collections.defaultdict(set)
        for (a, b) in prerequisites:
            fol[b].add(a)
            req[a].add(b)
        
        taken = [i for i in range(numCourses) if not req[i]]
        i = 0
        while i < len(taken):
            curr = taken[i]
            i += 1
            for c in fol[curr]:
                req[c].remove(curr)
                if not req[c]:
                    taken.append(c)
        
        return taken if len(taken) == numCourses else []

Indegree

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        indegree, fol = collections.defaultdict(int), collections.defaultdict(set)
        for (a, b) in prerequisites:
            fol[b].add(a)
            indegree[a] += 1
        
        taken = [i for i in range(numCourses) if not indegree[i]]
        i = 0
        while i < len(taken):
            curr = taken[i]
            i += 1
            for c in fol[curr]:
                indegree[c] -= 1
                if not indegree[c]:
                    taken.append(c)
        
        return taken if len(taken) == numCourses else []