介绍

拓扑排序，对于一个 DAG，每次去掉入度为 \(0\) 的边，最后将图去光，就是拓扑排序。

拓扑排序可以处理一些有序东西，比如在日常工作中，可能会将项目拆分成 \(A,B,C,D\) 四个子部分来完成，但 \(A\) 依赖于 \(B\) 和 \(D\)，\(C\) 依赖于 \(D\)（有先后顺序）。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。（\(\color{white}{\texttt{感觉像是个带依赖背包awa}}\)）

代码实现如下：

例题

1. NOIP2013普及T4 车站分级

题目中说，如果这趟车次停靠了火车站 \(x\)，则始发站、终点站之间所有级别大于等于火车站 \(x\) 的都必须停靠。也就是说，这趟车次经过且不停靠的所有车站的级别都必须小于这趟车次停靠的所有车站的级别\(\color{white}{\texttt{awa}}\)。

可以用有向图连接，由等级低的车站向等级高的车站连一条边，就是从低到高的，然后做个拓扑排序再统计下等级数即可\(\color{white}{\texttt{qaq}}\)。

2. 洛谷P1437 排序

几个增大不等式，显然可以建图跑拓扑。

若根据前 \(x\) 个关系即可确定这 \(n\) 个元素的顺序，输出
Sorted sequence determined after xxx relations: 顺序.（顺序不写符号，直接写字母）
若根据前 \(x\) 个关系即发现存在矛盾（如 \(A<B,B<C,C<A\)），输出
Inconsistency found after 2 relations.
若根据这 \(m\) 个关系无法确定这 \(n\) 个元素的顺序，输出
Sorted sequence cannot be determined.

  • 判第二个就是拓扑不完，也就是有环。
  • 判第三个就是拓扑时拓展了多个节点，导致这些同级的东西分不清。
  • 否则就是第一个。