拓扑排序_解题技巧
常见考点
判断有向图是否存在环
将结点个数、拓扑序列的元素个数二者对比，不等则说明存在环路
判断有向图的拓扑序列是否唯一
若唯一，无环且最长路等于节点数
n，默认情况下节点本身的长度为1。先要判环，随后有两种做法：
直接计算每个点的最长路，最后循环比较；常数略大但是没有逻辑坑点。
判断队列入度为0的元素个数是否大于1；
好写常数小，但是要注意逻辑坑点，有环情况、拓扑序列不唯一情况、无环且唯一三种情况的优先级处理！
根据一种、可传递的优先级规则（类似贪心），将有向图划分为若干个集合，并根据优先级按序处理各个集合
与并查集的异同
相同
有向无环图只能朝一个方向（反向不就带环了吗），只能根据一种、可传递的优先级规则进行分类
尽管并查集是无向图，且有扩展域并查集、边带权并查集两类
但根本上也是将各种状态合并为一种、且可传递的优先级规则
不同
有向无环图的结点整体分布是自上而下，且有向边的方向均朝下
并查集是不固定的森林结构，没有层次可言
练习题
- P1113 模板题+最长路
- P4017 模板题+最长路
- P1807 控制拓扑排序的起点
- P1347 验证拓扑序列是否唯一的经典题
- acwing-343 验证拓扑序列是否唯一的经典题
- P1983 模板题+最长路
- P8893 最长路
- P2712 最长路
- acwing-164 分层倒序处理+状态压缩