算法标签

拓扑排序、深度优先搜索（DFS）、贪心策略、图论

问题分析

题目需解决两个核心任务：一是构造满足两类限制的可行起飞序列，二是计算每个航班在所有可行序列中的最小起飞序号。两类限制分别为“航班i的起飞序号不超过k_i”和“航班a必须早于航班b起飞”（即a的序号小于b的序号）。

关键约束解读

1. 绝对约束：每个航班的起飞位置不能超出k_i的上限。
2. 相对约束：通过有向边(a,b)构建依赖关系，形成有向无环图（DAG），需保证拓扑序合规。

核心算法思路

一、可行起飞序列构造

1. 修正k_i值（依赖DFS）：

   • 构建正向依赖图（a→b表示a需早于b），通过DFS从无入度节点出发，反向更新每个节点的k_i。
   • 对于节点x，其k_i需取自身初始值与所有后继节点k_j-1的最小值，确保满足“x早于j”的约束（x的序号≤j的序号-1）。

2. 贪心构造序列：

   • 按修正后的k_i从小到大分组，同一k_i组内的航班无严格先后依赖。
   • 按k=1到k=n的顺序输出各组航班，确保所有航班的起飞序号不超过其k_i，且满足拓扑依赖（因k_i已修正为符合依赖的最大值）。

二、最小起飞序号计算

1. 反向依赖图与可达性分析：

   • 构建反向依赖图（b→a表示a需早于b，即b的前驱是a），通过DFS找到所有必须在航班i之前起飞的航班（即i的所有前驱及间接前驱）。

2. 统计最小序号：

   • 对于航班i，标记所有必须早于它的航班，剩余未标记的航班可在i之后起飞。
   • 从大到小遍历k分组，统计“无需早于i”的航班数量，最小序号=总航班数-无需早于i的航班数，确保i能占据最早可能的位置。

算法正确性与复杂度

正确性保障

• 修正k_i时，通过DFS确保所有依赖关系被满足，避免出现“后继节点序号≤当前节点”的矛盾。
• 贪心构造序列时，按k_i分组保证绝对约束，修正后的k_i已兼容相对约束，故序列合法。
• 最小序号计算通过反向可达性，准确统计必须前置的航班数，确保结果是所有可行序列中的最小值。

复杂度分析

• 时间复杂度：O(n+m)（DFS遍历图）+ O(n²)（最小序号计算时的多次DFS），适用于n≤2×10³、m≤10⁴的数据范围。
• 空间复杂度：O(n+m)（存储两张图的边和节点信息），空间开销可控。

总结

本题通过“修正约束+贪心构造”解决可行序列问题，通过“反向依赖+可达性统计”解决最小序号问题，核心是利用图论工具处理依赖关系，结合贪心策略满足两类约束，确保算法高效且正确。