LeetCode #210：课程表 II

1970-01-01 00:00 (GMT+8) 阅读时间 0 分钟 面试算法LeetCodeLeetCode-MediumPython拓扑排序DFS

https://leetcode.cn/problems/course-schedule-ii/description/

题目分析

标准的 DFS+染色算法。

题解

Python

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        g = defaultdict(list)
        for i, j in prerequisites:
            g[i].append(j)

        status = [0] * numCourses
        seq = []

        def dfs(i):  # 染色DFS
            # 维护一个染色状态， enum 没访问过, 成环, 已完全访问
            if status[i] == 2:  # 已完全访问
                return True
            if status[i] == 1:  # 成环
                return False
            # 还没访问过
            status[i] = 1 # 标记为已访问（下次再访问就成环）
            for nbr in g[i]:
                if not dfs(nbr):
                    return False  # 成环了
            status[i] = 2  # 把访问过的节点标记为已完全访问
            seq.append(i)
            return True

        for i in range(numCourses):
            if not dfs(i):
                return []

        return seq

页面历史

最后编辑于 6 天前

查看完整历史

5b8f47b-docs: 算法题解标签细化

b97e705-docs: add solution for LeetCode #210 - 课程表 II