拓扑排序
Kahn 算法
输出字典序最小的topsort
你可以直接使用这段文字，它简洁地概括了“字典序最小拓扑排序”的本质：
💡 核心总结：如何实现字典序最小的拓扑排序？
1. 核心工具：
将标准 Kahn 算法中的“队列”替换为**“小根堆（优先队列）”**。
2. 算法本质：
- 入度为 0 是前提：只有当一个节点的入度减为 0 时，才意味着它所有的前驱节点都已删除完毕。此时，该节点才具备进入序列的“资格”。
- 贪心策略是关键：在任何时刻，所有入度为 0 的节点都是彼此独立、可以随时输出的。为了让整体字典序最小，我们每次都从这群“自由节点”中，利用小根堆挑出编号最小的那一个优先输出。
3. 一句话证明：
- 由于进入堆的节点前驱已全部清空，它们之间不存在先后约束，因此“每一步都选最小的”这一局部最优解，最终会导向全局字典序最小的拓扑序。
- 进入堆是“前驱已全部删除”的充分必要条件。
dfs输出所有topsort
为了能求出所有的可能的topsort,这里使用dfs回溯法
-
类似 [走迷宫], 在一个分叉口,每个分叉的路线,我们都走一遍.
-
当回溯到这个路口的时候,我们要保证: 恢复现场,就像时间回溯到事情的开始,我们从新做一次选择.
练习题目
- P1113 topsort+DP
- P1347 判断topsort是不是唯一的,topsort是不是有环.
- P1685 topsort+DP
- P3243 反例说明：
, 限制为 。,需要思考,然后证明(直接暴力全排列,进行验证) : 反序列的字典序最大的topsort排列 - luogu-P1983 [NOIP 2013 普及组] 车站分级 tags: [noip,topsort] 根据题意思,教理相对等级模型
- P1038 toposrt +dp
- P4017 最大食物链计数 toposrt +dp
- P4934
- P2597