拓扑排序学习笔记

图论 学习笔记

学习笔记总览

$\mathbf{E}.$ 图论->$\textrm{A}.$ 拓扑排序。

发现自己线段树已经不会了，于是来捡一下拓扑排序，深究一下简单算法/hanx。

简介

定义一个排列 $p$ 为拓扑序当且仅当对于所有位置 $x<y$，满足 $p_y$ 无法在图上到达 $p_x$。

拓扑排序则可以在 $O(n+m)$ 的时间复杂度求出一种合法的拓扑序。

这里提一句，图的拓扑序计数是 P-complete 的，目前只有指数级算法，但是树/树形图/基环树的拓扑序计数均存在多项式级别算法。（例如P4099 [HEOI2013]SAO）

流程

1. 选择任意一个当前入度为 $0$ 的点 $x$。
2. 删除与 $x$ 相连的所有边，并更新其他点的入度。
3. 回到第一步，直到所有点都被遍历。

例题

例题 1 P7113 [NOIP2020] 排水系统
题意：自己读。
$1\leqslant n\leqslant 10^5$，$1\leqslant m\leqslant 10$，$0\leqslant d_i\leqslant 5$，数据保证污水从源到汇只会经过最多 $10$ 个中间节点。

憨憨题，考场上看着这个数字很大就写了个 $\text{unsigned long long}$，然后赚大了。

我们按照拓扑排序的流程模拟题意就好了，没有什么思维难度，要写高精度。

例题 2 P7077 [CSP-S2020] 函数调用
题意：一共有 $3$ 类函数，单点加，全局乘，以及调用其他的函数，给定一个函数执行序列，求出数组 $a$ 经过修改之后最终的结果。
$1\leqslant n,m,q\leqslant 10^5,1\leqslant\sum C_i\leqslant 10^6$，保证调用关系不会形成环

为啥我考场上想不出来这样的题目哇！orz hzr 秒掉

我们发现由于操作的特殊性，我们只需要输出 $a_i$ 乘全局乘的积与加法的贡献之和就好了。

如果 $x$ 调用 $y$，我们就让 $x$ 连一条到达 $y$ 的边，这样可以形成一个 DAG，我们只需要在这个 DAG 上 dp即可。

我们

例题 3 CF1385E Directing Edges
题意：给定一张 $n$ 个点 $m$ 条边的混合图，我们要给无向边定向，使得图无环，或者报告无解。
$1\leqslant n,m\leqslant 2\times 10^5$

太拉了，蹲了一个坑才想出来。

首先考虑没有有向边的情况，我们直接将编号小的点向编号大的点连边就不会有问题。

观察样例发现只有存在环的时候才无解，否则我们可以跑一遍拓扑排序，将拓扑序小的点向拓扑序大的点连边。

类似的题：CF1100E Andrew and Taxi（套个二分）

例题 4 CF915D Almost Acyclic Graph
题意：给定一张 $n$ 个点 $m$ 条边的有向图，去除至多一条边，使得图无环，或者报告无解。
$1\leqslant n\leqslant 500,1\leqslant m\leqslant 10^5$

首先我们有一个很简单的 $O(m^2)$ 解法，枚举每条边并删除，然后跑拓扑排序。

我们思考删边 $(x,y)$ 在拓扑排序中意味着什么，发现删边只会让 $y$ 的入度减一，且在拓扑排序中不再遍历这条边。

我们发现拓扑排序中不再遍历这条边是没有意义的，因为如果这条边再遍历一遍，也不会影响到已经入队的 $y$。

于是我们枚举每个点，让它入度减一，跑一遍拓扑排序就可以了，时间复杂度 $O(nm)$。

例题：（未分类）

P3244 [HNOI2015]落忆枫音

P6134 [JSOI2015]最小表示（P6954 [NEERC2017]Connections）

P6970 [NEERC2016]Game on Graph

AT4380 [AGC027F] Grafting

AT2306 [AGC010E] Rearranging

CF1142E Pink Floyd

CF1476E Pattern Matching

AT1984 [AGC001F] Wide Swap

CF1477D Nezzar and Hidden Permutations

P3953 [NOIP2017 提高组] 逛公园

P5400 [CTS2019]随机立方体

P3573 [POI2014]RAJ-Rally

P3588 [POI2015] PUS