LeetCode 1203 项目管理用双层拓扑排序解决「分组 依赖」混合约束问题【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术文章基于 leetcode 题解仓库中的题解文档 1203. 项目管理 展开系统讲解一道 Hard 级图论题「1203. 项目管理Sort Items by Groups Respecting Dependencies」的完整解法。读完本篇你将掌握如何将题目中「项目内依赖 小组间依赖」的混合约束拆分为两层层级的有向图使用 Kahn 算法BFS 拓扑排序完成排序并理解 DFS 拓扑排序、无人负责项目的分组技巧与环检测判定的全部实现细节。一、题目背景与完整需求公司共有 n 个项目和 m 个小组每个项目要么无人接手要么由 m 个小组之一负责。给定两个输入group[i]第 i 个项目所属的小组编号若该项目目前无人接手则group[i] -1项目和小组都从零开始编号。小组也可能没有接手任何项目beforeItems项目依赖列表其中beforeItems[i]表示在进行第 i 个项目之前位于第 i 个项目左侧必须完成的所有项目。要求安排这些项目的进度并返回排序后的项目列表约束如下同一小组的项目排序后在列表中必须彼此相邻所有beforeItems给出的依赖关系必须满足被依赖者排在依赖者左侧若存在多个合法方案返回其中任意一个即可若不存在合法方案返回空列表[]。两个官方示例继承自原题解文档示例 1输入n 8, m 2, group [-1,-1,1,0,0,1,0,-1], beforeItems [[],[6],[5],[6],[3,6],[],[],[]] 输出[6,3,4,1,5,2,0,7]示例 2输入n 8, m 2, group [-1,-1,1,0,0,1,0,-1], beforeItems [[],[6],[5],[3],[],[],[4],[]] 输出[] 解释与示例 1 大致相同但是在排序后的列表中4 必须放在 6 的前面。示例 2 之所以无解关键在于依赖边被移动后产生了循环依赖6 依赖 44 又依赖 6导致无法形成合法的拓扑序。数据范围提示1 m n 3 * 10^4 group.length beforeItems.length n -1 group[i] m - 1 0 beforeItems[i].length n - 1 0 beforeItems[i][j] n - 1 i ! beforeItems[i][j] beforeItems[i] 不含重复元素这道题在原题解文档中被明确标注为「不简单」因为它隐藏了三个考点拓扑排序本身、跨组依赖关系的推导、无人负责项目的处理。下文逐一展开。二、前置知识拓扑排序的两种实现方式题解文档给出的前置知识是「图论 - 拓扑排序」与「BFS DFS」。当前仓库的知识库文档 图论专题 对拓扑排序有一个更完整的定义可与本题解法互为印证有向图的拓扑排序是对其顶点的一种线性排序使得对于从顶点 u 到顶点 v 的每个有向边 uvu 在排序中都在之前。当且仅当图中没有定向环时即有向无环图 DAG才有可能进行拓扑排序。任何有向无环图至少有一个拓扑排序且存在线性时间复杂度的算法来构建它。该文档在 Kahn 算法一节 给出的核心流程是先找到所有入度为零的节点放入结果列表 L它们没有任何前驱然后把与这些节点相连的边从图中「去掉」即下游节点入度减一再寻找新的入度为零的节点重复直到找不到入度为零的节点为止。若 L 中元素个数与节点总数相同则排序完成否则说明原图中存在环无法拓扑排序。DFS 专题文档 也指出深度优先搜索可以产生目标图的拓扑排序表。围绕 1203 这道题原题解文档总结了两种实现路线两者在完整代码中都会用到路线 ABFSKahn 算法从入度为 0 的节点没有任何依赖出发将其邻居依赖它的节点逐步加入队列并将邻居入度减 1入度减到 0 说明已无依赖入队处理。这种做法不需要 visited 数组——因为环上的节点入度永远不可能为 0自然不会被入队也就不会死循环。def tp_sort(self, items, indegree, neighbors): q collections.deque([]) ans [] for item in items: if not indegree[item]: q.append(item) while q: cur q.popleft() ans.append(cur) for neighbor in neighbors[cur]: indegree[neighbor] - 1 if not indegree[neighbor]: q.append(neighbor) return ans注意这个通用函数的设计它只接收「待排序节点集合items、入度表indegree、邻接表neighbors」三个参数与具体业务无关因此同一份代码可以分别用于「组级别图」和「项目级别图」两次拓扑排序。若返回长度小于len(items)说明存在环调用方应判定无解。路线 BDFS后序记录 三态标记DFS 方式可以从图的任意一点出发基于深度优先遍历检测环若检测到环则返回[]否则将遍历后序得到的 path 直接作为拓扑序返回。此方法需要 visited 数组取值含义为0未访问、1访问中在当前递归栈内、2已完成。遇到visited[i] 1说明回溯到了递归栈内的节点即存在环class Solution: def tp_sort(self, items: int, pres: List[List[int]]) - List[int]: res [] visited [0] * items adjacent [[] for _ in range(items)] def dfs(i): if visited[i] 1: return False if visited[i] 2: return True visited[i] 1 for j in adjacent[i]: if not dfs(j): return False visited[i] 2 res.append(i) return True for cur, pre in pres: adjacent[cur].append(pre) for i in range(items): if not dfs(i): return [] return res与本题解最终采用的 Kahn 实现相比DFS 版本需要显式维护三态访问标记来识别「当前递归栈内的节点」而 BFS 版本天然依赖入度约束规避环。两种写法在复杂度上都是 O(V E)。相关经典题目是课程系列的两道入门题210. 课程表 II、207. 课程表它们只涉及单层依赖图而 1203 的难点在于图被拆分成了「组」与「项目」两层。三、考点二依赖关系如何拆分——边染色是本题的灵魂原题解文档用「边染色」的方式描述了建图过程原文配图无法随仓库查看此处按文字描述重建语义圆圈表示项目黑色线条表示项目之间的依赖关系即beforeItems中两端项目属于同一小组的情况红色线条表示项目和组之间的依赖关系两端分属不同组时依赖被提升到组级别绿色线条表示组与组之间的依赖关系——注意这部分不是题目直接给出的而是需要我们自己推导生成这也是本题最大的思维陷阱。生成绿色边组间依赖的核心逻辑只有一句话如果一个项目和它的某个依赖如果存在分属不同的组那么这两个组之间就拥有依赖关系。对应到建图代码for pre in pres[project]: if group[pre] ! group[project]: # 小组关系图 group_indegree[group[project]] 1 group_neighbors[group[pre]].append(group[project]) else: # 项目关系图 # 见下文完整代码其中pres即题目输入beforeItems表示项目依赖关系。这段逻辑的含义需要仔细理解当依赖边两端项目同组时依赖落在「项目图」里project_indegree[project] 1并在项目邻接表中连边pre - project。这类边决定同一小组内部项目的先后顺序当依赖边两端项目跨组时由于「同组项目必须相邻」的硬性约束跨组依赖被压缩为两个组之间的先后关系group_indegree[group[project]] 1并连组级边group[pre] - group[project]。也就是说组 G1 中任意项目依赖组 G2 中的项目等价于「G1 整组必须排在 G2 整组之后」这正是保证同组项目彼此相邻的数学保障。一个值得注意的细节跨组边只加一次组级入度而不需要为组内每个具体项目重复累加。因为组级拓扑排序通过后才轮到组内项目排序跨组依赖已在组层面被一次性「结算」。四、考点三无人负责的项目如何并入拓扑图group[i] -1表示项目目前无人接手。原题解文档给出的处理思路是既然没有组那就随便分配一个组让该项目成为「只含自己一个项目的独立小组」。具体实现是给这些项目各分配一个不重复的新组 id——由于原有组 id 范围是[0, m-1]新 id 从m开始逐个自增即可max_group_id m for project in range(n): if group[project] -1: group[project] max_group_id max_group_id 1这一步至关重要原因有二分配后的组在组级别图中没有任何入边是天然的入度为零节点不会引入任何虚假依赖满足「无人接手 可随意安排」的语义每个无组项目独占一个组组内只有一个项目组内拓扑排序退化为恒等最终输出中这些项目自然散落在合法位置且不会破坏其他组的相邻性。处理完后整个系统中最多有max_group_id≤ n个组每个项目恰好属于一个组。五、完整解法代码Python3以下是原题解文档给出的完整实现支持 Python3此处保留全部逻辑并补充逐段注释class Solution: def tp_sort(self, items, indegree, neighbors): 通用 Kahn 算法对 items 中的节点做拓扑排序返回拓扑序。 若返回长度小于 len(items)说明存在环调用方应判定无解。 q collections.deque([]) ans [] for item in items: if not indegree[item]: q.append(item) while q: cur q.popleft() ans.append(cur) for neighbor in neighbors[cur]: indegree[neighbor] - 1 if not indegree[neighbor]: q.append(neighbor) return ans def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) - List[int]: # 考点三无组项目各分配一个从 m 开始的独立新组 max_group_id m for project in range(n): if group[project] -1: group[project] max_group_id max_group_id 1 project_indegree collections.defaultdict(int) group_indegree collections.defaultdict(int) project_neighbors collections.defaultdict(list) group_neighbors collections.defaultdict(list) group_projects collections.defaultdict(list) for project in range(n): # 记录每个组包含哪些项目 group_projects[group[project]].append(project) for pre in pres[project]: if group[pre] ! group[project]: # 考点二跨组依赖 —— 组关系图绿色边 group_indegree[group[project]] 1 group_neighbors[group[pre]].append(group[project]) else: # 考点二组内依赖 —— 项目关系图黑色边 project_indegree[project] 1 project_neighbors[pre].append(project) ans [] # 第一层对组级别图做拓扑排序 group_queue self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors) # 组图有环 无合法方案 if len(group_queue) ! max_group_id: return [] # 第二层按组的拓扑序依次对每个组内的项目做拓扑排序 for group_id in group_queue: project_queue self.tp_sort(group_projects[group_id], project_indegree, project_neighbors) # 组内项目有环 无合法方案 if len(project_queue) ! len(group_projects[group_id]): return [] ans project_queue return ans整体结构可以概括为「两次拓扑排序」第一层组图节点是所有组 id[0, max_group_id)边来自跨组依赖用通用tp_sort得到组的合法先后顺序若组图排序长度不等于组总数说明组间存在循环依赖直接返回[]示例 2 正是死在这一层6 依赖 4 且 4 依赖 6跨组边成环第二层项目图严格沿着组的拓扑序对每个组的项目集合调用同一个tp_sort得到组内项目的合法顺序若某个组内排序长度不足说明组内存在环同样返回[]将每个组排好的项目依次拼接即为最终答案。因为组的顺序本身合法且同组项目必然连续输出两个核心约束依赖满足 同组相邻同时成立。从源码结构看两个defaultdict分别维护组图与项目图的入度和邻接表边按「跨组/组内」二选一分流互不污染group_projects字典则负责把第一层的组顺序翻译成第二层要遍历的项目集合是连接两层的桥梁。六、正确性推演以示例 1 为例用示例 1 手动推演一遍验证算法行为输入n 8, m 2, group [-1,-1,1,0,0,1,0,-1], beforeItems [[],[6],[5],[6],[3,6],[],[],[]]第 0、1、7 号项目无组分别被分配新组 id 2、3、4于是max_group_id 5共 5 个组组 0 {3, 4, 6}组 1 {2, 5}组 2 {0}组 3 {1}组 4 {7}逐条扫描依赖边pre - project项目 1 依赖 6组 3 与组 0 跨组连组边 0 - 3组 3 入度 1项目 2 依赖 5同属组 1连项目边 5 - 2项目 2 入度 1项目 3 依赖 6同属组 0连项目边 6 - 3项目 3 入度 1项目 4 依赖 3、6同属组 0连项目边 3 - 4、6 - 4项目 4 入度 2组图入度组 3 入度 1其余组入度 0。组拓扑序可以是[0, 1, 2, 4, 3]的某种合法排列如 0 先出队按组顺序做组内排序组 0 内 6 - 3 - 4入度驱动组 1 内 5 - 2组 2/3/4 各自单元素拼接结果形如[6, 3, 4, 1, 5, 2, 0, 7]组的出队顺序不同会得到其他合法排列与题目示例输出一致。示例 2 中依赖边被改为「4 依赖 6、6 依赖 4」两者同属组 0产生组内项目边 6 - 4 与 4 - 6组 0 的项目拓扑排序返回长度 2 组内项目数 3 时触发环检测实际是 4、6 两个项目互锁项目 3 入度永远无法归零最终返回[]与题目期望一致。七、复杂度分析原题解文档给出的结论令 m 和 n 分别为图的边数和顶点数时间复杂度O(m n)。建图遍历 n 个项目和所有依赖边一次两次 Kahn 排序各自线性扫描自己那层的节点与边总工作量与节点数加边数成线性关系空间复杂度O(m n)。入度表、邻接表、组项目映射与队列的总规模由节点和边决定。结合题目数据范围n 3 * 10^4线性复杂度完全可承受最坏输入。八、在仓库中的定位与延伸阅读本篇题解在当前仓库中的组织方式可供参考题解原文位于 problems/1203.sort-items-by-groups-respecting-dependencies.md并收录于 Hard 难度题解汇总 与 SUMMARY.md 目录、introduction.md 题目清单中仓库的题解写作规范见 题解提交模板要求每篇题解至少包含题目地址、题目描述、前置知识、思路、代码等章节本篇文档的结构即严格遵循了该模板拓扑排序的更一般化讲解定义、Kahn 算法的完整 Python 实现、环判定标准可在 图论专题 的「拓扑排序」小节找到DFS 专题 则补充了基于深度优先搜索生成拓扑序表的视角。对想继续深入本类问题的读者建议的练习路径是先完成课程系列207 课程表、210 课程表 II熟悉单层图的环检测与排序再来挑战 1203 的「两层图」结构——核心方法论始终不变先把隐式约束显式化为有向边再对每一层分别运行通用拓扑排序用「排序结果长度 节点总数」作为统一的判环与无解依据。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 1203 项目管理：用双层拓扑排序解决「分组 + 依赖」混合约束问题
LeetCode 1203 项目管理用双层拓扑排序解决「分组 依赖」混合约束问题【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术文章基于 leetcode 题解仓库中的题解文档 1203. 项目管理 展开系统讲解一道 Hard 级图论题「1203. 项目管理Sort Items by Groups Respecting Dependencies」的完整解法。读完本篇你将掌握如何将题目中「项目内依赖 小组间依赖」的混合约束拆分为两层层级的有向图使用 Kahn 算法BFS 拓扑排序完成排序并理解 DFS 拓扑排序、无人负责项目的分组技巧与环检测判定的全部实现细节。一、题目背景与完整需求公司共有 n 个项目和 m 个小组每个项目要么无人接手要么由 m 个小组之一负责。给定两个输入group[i]第 i 个项目所属的小组编号若该项目目前无人接手则group[i] -1项目和小组都从零开始编号。小组也可能没有接手任何项目beforeItems项目依赖列表其中beforeItems[i]表示在进行第 i 个项目之前位于第 i 个项目左侧必须完成的所有项目。要求安排这些项目的进度并返回排序后的项目列表约束如下同一小组的项目排序后在列表中必须彼此相邻所有beforeItems给出的依赖关系必须满足被依赖者排在依赖者左侧若存在多个合法方案返回其中任意一个即可若不存在合法方案返回空列表[]。两个官方示例继承自原题解文档示例 1输入n 8, m 2, group [-1,-1,1,0,0,1,0,-1], beforeItems [[],[6],[5],[6],[3,6],[],[],[]] 输出[6,3,4,1,5,2,0,7]示例 2输入n 8, m 2, group [-1,-1,1,0,0,1,0,-1], beforeItems [[],[6],[5],[3],[],[],[4],[]] 输出[] 解释与示例 1 大致相同但是在排序后的列表中4 必须放在 6 的前面。示例 2 之所以无解关键在于依赖边被移动后产生了循环依赖6 依赖 44 又依赖 6导致无法形成合法的拓扑序。数据范围提示1 m n 3 * 10^4 group.length beforeItems.length n -1 group[i] m - 1 0 beforeItems[i].length n - 1 0 beforeItems[i][j] n - 1 i ! beforeItems[i][j] beforeItems[i] 不含重复元素这道题在原题解文档中被明确标注为「不简单」因为它隐藏了三个考点拓扑排序本身、跨组依赖关系的推导、无人负责项目的处理。下文逐一展开。二、前置知识拓扑排序的两种实现方式题解文档给出的前置知识是「图论 - 拓扑排序」与「BFS DFS」。当前仓库的知识库文档 图论专题 对拓扑排序有一个更完整的定义可与本题解法互为印证有向图的拓扑排序是对其顶点的一种线性排序使得对于从顶点 u 到顶点 v 的每个有向边 uvu 在排序中都在之前。当且仅当图中没有定向环时即有向无环图 DAG才有可能进行拓扑排序。任何有向无环图至少有一个拓扑排序且存在线性时间复杂度的算法来构建它。该文档在 Kahn 算法一节 给出的核心流程是先找到所有入度为零的节点放入结果列表 L它们没有任何前驱然后把与这些节点相连的边从图中「去掉」即下游节点入度减一再寻找新的入度为零的节点重复直到找不到入度为零的节点为止。若 L 中元素个数与节点总数相同则排序完成否则说明原图中存在环无法拓扑排序。DFS 专题文档 也指出深度优先搜索可以产生目标图的拓扑排序表。围绕 1203 这道题原题解文档总结了两种实现路线两者在完整代码中都会用到路线 ABFSKahn 算法从入度为 0 的节点没有任何依赖出发将其邻居依赖它的节点逐步加入队列并将邻居入度减 1入度减到 0 说明已无依赖入队处理。这种做法不需要 visited 数组——因为环上的节点入度永远不可能为 0自然不会被入队也就不会死循环。def tp_sort(self, items, indegree, neighbors): q collections.deque([]) ans [] for item in items: if not indegree[item]: q.append(item) while q: cur q.popleft() ans.append(cur) for neighbor in neighbors[cur]: indegree[neighbor] - 1 if not indegree[neighbor]: q.append(neighbor) return ans注意这个通用函数的设计它只接收「待排序节点集合items、入度表indegree、邻接表neighbors」三个参数与具体业务无关因此同一份代码可以分别用于「组级别图」和「项目级别图」两次拓扑排序。若返回长度小于len(items)说明存在环调用方应判定无解。路线 BDFS后序记录 三态标记DFS 方式可以从图的任意一点出发基于深度优先遍历检测环若检测到环则返回[]否则将遍历后序得到的 path 直接作为拓扑序返回。此方法需要 visited 数组取值含义为0未访问、1访问中在当前递归栈内、2已完成。遇到visited[i] 1说明回溯到了递归栈内的节点即存在环class Solution: def tp_sort(self, items: int, pres: List[List[int]]) - List[int]: res [] visited [0] * items adjacent [[] for _ in range(items)] def dfs(i): if visited[i] 1: return False if visited[i] 2: return True visited[i] 1 for j in adjacent[i]: if not dfs(j): return False visited[i] 2 res.append(i) return True for cur, pre in pres: adjacent[cur].append(pre) for i in range(items): if not dfs(i): return [] return res与本题解最终采用的 Kahn 实现相比DFS 版本需要显式维护三态访问标记来识别「当前递归栈内的节点」而 BFS 版本天然依赖入度约束规避环。两种写法在复杂度上都是 O(V E)。相关经典题目是课程系列的两道入门题210. 课程表 II、207. 课程表它们只涉及单层依赖图而 1203 的难点在于图被拆分成了「组」与「项目」两层。三、考点二依赖关系如何拆分——边染色是本题的灵魂原题解文档用「边染色」的方式描述了建图过程原文配图无法随仓库查看此处按文字描述重建语义圆圈表示项目黑色线条表示项目之间的依赖关系即beforeItems中两端项目属于同一小组的情况红色线条表示项目和组之间的依赖关系两端分属不同组时依赖被提升到组级别绿色线条表示组与组之间的依赖关系——注意这部分不是题目直接给出的而是需要我们自己推导生成这也是本题最大的思维陷阱。生成绿色边组间依赖的核心逻辑只有一句话如果一个项目和它的某个依赖如果存在分属不同的组那么这两个组之间就拥有依赖关系。对应到建图代码for pre in pres[project]: if group[pre] ! group[project]: # 小组关系图 group_indegree[group[project]] 1 group_neighbors[group[pre]].append(group[project]) else: # 项目关系图 # 见下文完整代码其中pres即题目输入beforeItems表示项目依赖关系。这段逻辑的含义需要仔细理解当依赖边两端项目同组时依赖落在「项目图」里project_indegree[project] 1并在项目邻接表中连边pre - project。这类边决定同一小组内部项目的先后顺序当依赖边两端项目跨组时由于「同组项目必须相邻」的硬性约束跨组依赖被压缩为两个组之间的先后关系group_indegree[group[project]] 1并连组级边group[pre] - group[project]。也就是说组 G1 中任意项目依赖组 G2 中的项目等价于「G1 整组必须排在 G2 整组之后」这正是保证同组项目彼此相邻的数学保障。一个值得注意的细节跨组边只加一次组级入度而不需要为组内每个具体项目重复累加。因为组级拓扑排序通过后才轮到组内项目排序跨组依赖已在组层面被一次性「结算」。四、考点三无人负责的项目如何并入拓扑图group[i] -1表示项目目前无人接手。原题解文档给出的处理思路是既然没有组那就随便分配一个组让该项目成为「只含自己一个项目的独立小组」。具体实现是给这些项目各分配一个不重复的新组 id——由于原有组 id 范围是[0, m-1]新 id 从m开始逐个自增即可max_group_id m for project in range(n): if group[project] -1: group[project] max_group_id max_group_id 1这一步至关重要原因有二分配后的组在组级别图中没有任何入边是天然的入度为零节点不会引入任何虚假依赖满足「无人接手 可随意安排」的语义每个无组项目独占一个组组内只有一个项目组内拓扑排序退化为恒等最终输出中这些项目自然散落在合法位置且不会破坏其他组的相邻性。处理完后整个系统中最多有max_group_id≤ n个组每个项目恰好属于一个组。五、完整解法代码Python3以下是原题解文档给出的完整实现支持 Python3此处保留全部逻辑并补充逐段注释class Solution: def tp_sort(self, items, indegree, neighbors): 通用 Kahn 算法对 items 中的节点做拓扑排序返回拓扑序。 若返回长度小于 len(items)说明存在环调用方应判定无解。 q collections.deque([]) ans [] for item in items: if not indegree[item]: q.append(item) while q: cur q.popleft() ans.append(cur) for neighbor in neighbors[cur]: indegree[neighbor] - 1 if not indegree[neighbor]: q.append(neighbor) return ans def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) - List[int]: # 考点三无组项目各分配一个从 m 开始的独立新组 max_group_id m for project in range(n): if group[project] -1: group[project] max_group_id max_group_id 1 project_indegree collections.defaultdict(int) group_indegree collections.defaultdict(int) project_neighbors collections.defaultdict(list) group_neighbors collections.defaultdict(list) group_projects collections.defaultdict(list) for project in range(n): # 记录每个组包含哪些项目 group_projects[group[project]].append(project) for pre in pres[project]: if group[pre] ! group[project]: # 考点二跨组依赖 —— 组关系图绿色边 group_indegree[group[project]] 1 group_neighbors[group[pre]].append(group[project]) else: # 考点二组内依赖 —— 项目关系图黑色边 project_indegree[project] 1 project_neighbors[pre].append(project) ans [] # 第一层对组级别图做拓扑排序 group_queue self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors) # 组图有环 无合法方案 if len(group_queue) ! max_group_id: return [] # 第二层按组的拓扑序依次对每个组内的项目做拓扑排序 for group_id in group_queue: project_queue self.tp_sort(group_projects[group_id], project_indegree, project_neighbors) # 组内项目有环 无合法方案 if len(project_queue) ! len(group_projects[group_id]): return [] ans project_queue return ans整体结构可以概括为「两次拓扑排序」第一层组图节点是所有组 id[0, max_group_id)边来自跨组依赖用通用tp_sort得到组的合法先后顺序若组图排序长度不等于组总数说明组间存在循环依赖直接返回[]示例 2 正是死在这一层6 依赖 4 且 4 依赖 6跨组边成环第二层项目图严格沿着组的拓扑序对每个组的项目集合调用同一个tp_sort得到组内项目的合法顺序若某个组内排序长度不足说明组内存在环同样返回[]将每个组排好的项目依次拼接即为最终答案。因为组的顺序本身合法且同组项目必然连续输出两个核心约束依赖满足 同组相邻同时成立。从源码结构看两个defaultdict分别维护组图与项目图的入度和邻接表边按「跨组/组内」二选一分流互不污染group_projects字典则负责把第一层的组顺序翻译成第二层要遍历的项目集合是连接两层的桥梁。六、正确性推演以示例 1 为例用示例 1 手动推演一遍验证算法行为输入n 8, m 2, group [-1,-1,1,0,0,1,0,-1], beforeItems [[],[6],[5],[6],[3,6],[],[],[]]第 0、1、7 号项目无组分别被分配新组 id 2、3、4于是max_group_id 5共 5 个组组 0 {3, 4, 6}组 1 {2, 5}组 2 {0}组 3 {1}组 4 {7}逐条扫描依赖边pre - project项目 1 依赖 6组 3 与组 0 跨组连组边 0 - 3组 3 入度 1项目 2 依赖 5同属组 1连项目边 5 - 2项目 2 入度 1项目 3 依赖 6同属组 0连项目边 6 - 3项目 3 入度 1项目 4 依赖 3、6同属组 0连项目边 3 - 4、6 - 4项目 4 入度 2组图入度组 3 入度 1其余组入度 0。组拓扑序可以是[0, 1, 2, 4, 3]的某种合法排列如 0 先出队按组顺序做组内排序组 0 内 6 - 3 - 4入度驱动组 1 内 5 - 2组 2/3/4 各自单元素拼接结果形如[6, 3, 4, 1, 5, 2, 0, 7]组的出队顺序不同会得到其他合法排列与题目示例输出一致。示例 2 中依赖边被改为「4 依赖 6、6 依赖 4」两者同属组 0产生组内项目边 6 - 4 与 4 - 6组 0 的项目拓扑排序返回长度 2 组内项目数 3 时触发环检测实际是 4、6 两个项目互锁项目 3 入度永远无法归零最终返回[]与题目期望一致。七、复杂度分析原题解文档给出的结论令 m 和 n 分别为图的边数和顶点数时间复杂度O(m n)。建图遍历 n 个项目和所有依赖边一次两次 Kahn 排序各自线性扫描自己那层的节点与边总工作量与节点数加边数成线性关系空间复杂度O(m n)。入度表、邻接表、组项目映射与队列的总规模由节点和边决定。结合题目数据范围n 3 * 10^4线性复杂度完全可承受最坏输入。八、在仓库中的定位与延伸阅读本篇题解在当前仓库中的组织方式可供参考题解原文位于 problems/1203.sort-items-by-groups-respecting-dependencies.md并收录于 Hard 难度题解汇总 与 SUMMARY.md 目录、introduction.md 题目清单中仓库的题解写作规范见 题解提交模板要求每篇题解至少包含题目地址、题目描述、前置知识、思路、代码等章节本篇文档的结构即严格遵循了该模板拓扑排序的更一般化讲解定义、Kahn 算法的完整 Python 实现、环判定标准可在 图论专题 的「拓扑排序」小节找到DFS 专题 则补充了基于深度优先搜索生成拓扑序表的视角。对想继续深入本类问题的读者建议的练习路径是先完成课程系列207 课程表、210 课程表 II熟悉单层图的环检测与排序再来挑战 1203 的「两层图」结构——核心方法论始终不变先把隐式约束显式化为有向边再对每一层分别运行通用拓扑排序用「排序结果长度 节点总数」作为统一的判环与无解依据。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考