拓扑序

Vision271 · 2022-09-22 08:46:52 · 个人记录

概述

拓扑序

• 在有向无环图上,将所有点的编号排成的一个序列,使得 \forall u,v,\exists e_{u\to v},s.t.u<v。

• 显然，同一幅 DAG 的拓扑序可能有复数个。

• 按拓扑序拆边进行 dp（通常是顺推），一定没有后效性。

• 拓扑序的本质：

  • 一种“序”，一种从多个偏序关系推出的元素之间的序。和单增，单降之类的序，并没有本质区别。

  • 它之所以是“拓扑序”，就是因为它可以抽象为一种图论模型，这一模型下元素之间的偏序关系被抽象为有向边。

  • 故其可以用于验证某个元素集是否能够满足某种偏序关系，典型代表如 \text{ABC277F Sorting a Matrix}。

实现原理

• 不断顺推拆边，拆没了就加进队列，很类似于 bfs。O(n+m)。

• 如何求字典序最小的拓扑序？只要把手写的队列换成 priority_queue 就可以了。O(m\log m)。

int n,m,in[maxn],q[maxn],hd=1,tl;
b_s<int> e[maxn];
void toposort(){
    For(i,1,n) if(!in[i]) q[++tl]=i;
    while(tl>=hd){
        int now=q[hd++];
        for(int a:e[now]){
            --in[a];某种想做的操作;
            if(!in[a]) q[++tl]=a;
        }
    }
}

应用

• 事实上,最后出来的拓扑序列，大部分情况下本身什么用都没有（还是有一点，比如说检验一个有向图是否无环，环上点永远进不了 q）。

• 我们往往是借它的壳（转移顺序），做一些自己的事情。

• 最常见的就是 dp：

  • 转移好设计的时候，我们通常用朴素的递推/逆推。

  • 不好设计时就是记忆化搜索（模糊掉拓扑序,倒序解除依赖关系），或者边拓扑排序边做。

例题

• \text{P4017 最大食物链计数}
• \text{P1038 [NOIP2003 提高组] 神经网络}
• \text{P1137 旅行计划}