P3750. 启动多任务排序

解题思路

看到存在依赖关系，立马想到拓扑排序。

本题一个小难点在于如何对同级节点进行排序。

在 BFS 每一层搜索之前，可以构建一个空数组 nodes_new，来储存搜索过程中新出现的入度为 0 的节点。这些新出现的节点属于拓扑排序中的同级节点，需要在 for 循环结束后进行排序，然后加入到 ans 中。

代码如下：

思路展开 把「任务 A 依赖任务 B」看成图中一条从 B 指向 A 的边，问题就变成拓扑排序：入度为 0 的任务没有任何未完成的前置，可以立刻执行。代码用 neighbor_dic 存邻接表（key 是被依赖方 b，value 是依赖它的任务列表），用 indegree_dic 记每个任务的入度。初始答案 ans 取所有入度为 0 的节点并按字典序排序，同时作为 BFS 队列的第一层。之后逐层推进：弹出当前层的每个任务 cur_node，把它的每个后继 nxt_node 的入度减一，表示「又一个前置完成了」；入度降为 0 的后继收进临时列表 nodes_new 并入队。关键的一步是每层循环结束后，先对 nodes_new 按字典序排序再拼接到 ans 后面——同一层的任务是「同时变为可执行」的，题目规定这种情况按任务名称的字母顺序执行，逐层排序正好实现了这条贪婪规则。队列清空后，ans 就是完整的执行顺序。

复杂度分析 设任务（节点）总数为 V、依赖关系（边）数为 E。解析输入并构建邻接表与入度表为 O(E)；拓扑排序主体中每个节点至多入队出队一次、每条边恰好使入度减一一次，为 O(V + E)；排序方面，初始层与各层的 nodes_new 互不重叠，所有层排序的总代价不超过 O(V log V)。总时间复杂度 O(V log V + E)，瓶颈在分层排序与遍历所有依赖边。空间上，邻接表与入度表共 O(V + E)，队列和 ans 至多 O(V)，空间复杂度 O(V + E)。