動機

複習dfs 話說原來有擋修是這麼麻煩的事

Problem

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] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

  • 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.

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]Output: trueExplanation: 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: falseExplanation: 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.

 

Constraints:

  • 1 <= numCourses <= 105
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.

Sol

區分每堂課為

  1. ok可以上
  2. check中
  3. 還沒check

之後去走，如果遇到check中的就是出事

class Solution:
    def canFinish(self, cnt: int, pres: List[List[int]]) -> bool:
        def cache_computing(f,is_computing=None):
            mem = {}
            @functools.wraps(f)
            def wrapper(*args,**kwds):
                if args not in mem:
                    mem[args] = is_computing
                    mem[args] = f(*args,**kwds)
                return mem[args]
            return wrapper
        
        premises = defaultdict(list) # class, [premises]
        [premises[c].append(p) for (p,c) in pres]
        nofrees = tuple(premises.keys())
        frees = set(range(cnt)) - set(nofrees)
        
        @cache_computing
        def cycle(i):
            if i in frees:
                return False
            else:
                return any([((cycle(c) is None) or cycle(c)) for c in premises[i]])
        
        return not any([cycle(c) for c in nofrees])