2022年末刷题笔记

113.课程顺序

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = collections.defaultdict(list)
        for info in prerequisites:
            graph[info[1]].append(info[0]) 
        valid = True
        visited = [0] * numCourses
        result = []
        def dfs(u):
            nonlocal valid, result
            visited[u] = 1 # 搜索中
            for v in graph[u]:
                if visited[v] == 1: # 有环
                    valid = False
                    return 
                elif visited[v] == 2: # 已经完成v的搜索
                    ...
                else:
                    dfs(v)
                    if not valid:
                        return
            result.append(u)
            visited[u] = 2 # 标记为已完成搜索
        for idx in range(numCourses):
            if valid and visited[idx]==0:
                dfs(idx)
        # print(result, valid, visited)
        if valid:
            return result[::-1]
        else:
            return []

拓扑排序：如果节点之间有依赖关系，则拓扑排序要求记录的节点在前面出现的必须是后面出现的依赖项。因此用栈记录最深的节点，依次回溯节点，将栈的倒序输出即可。
另外。如果图中有环，则失败。用visited记录节点状态：0未所搜，1正在搜索，但没有回溯到该节点；·2搜索完毕。如果下一个节点的状态已经为1，则说明有环。