Graph

207. Course Schedule

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        #  [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi ，也就是 bi --- >ai
        edges = {i:[] for i in range(numCourses)}
        in_degrees = [0 for _ in range(numCourses)]   # in_degrees[i]记录节点i的入度

        for i, j in prerequisites:
            edges[j].append(i)
            in_degrees[i] += 1
        
        # 2. 将入度为0的所有节点都入队
        que, cnt = deque([]), 0
        for i in range(numCourses):
            if in_degrees[i] == 0:
                que.append(i)
        
        # 3. 出队入度为0的节点
        while que:
            node = que.popleft()
            cnt += 1

            for nb in edges[node]:
                in_degrees[nb] -= 1
                if in_degrees[nb] == 0:
                    que.append(nb)
        
        return len(que) == 0 and cnt == numCourses

797. 所有可能的路径

时间复杂度：2^n * n

空间复杂度：2^n * n

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        n = len(graph)
        res = []
        paths = [[0]]
        while paths:
            temp = []
            for path in paths:
                if path[-1] == n - 1:
                    res.append(path)
                    continue
                
                for node in graph[path[-1]]:
                    temp.append(path + [node])
            paths = temp
        
        return res