拓扑排序

在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序(英语:Topological sorting)。

  1. 每个顶点出现且只出现一次;
  2. 若A在序列中排在B的前面,则在图中不存在从B到A的路径。
    也可以定义为:拓扑排序是对有向无环图的顶点的一种排序,其中如果图中从A到B有边(注意A到B有边那么B到A必然没有边),那么在排序中A出现在B的前面。注意拓扑排序并不一定存在,例如当图中存在环时。

拓扑排序的一种实现方式就是对每个点维护它的入度。我们假设图已经建好,如果从A到B有边,那么我们要把A放到B的前面,容易发现一个点的入度越高,那么它的前置条件也就越多。每次选取任意一个入度为0的点,然后删掉它的所有出边,更新入度。
容易看拓扑排序的结果是不固定的,因为可能同时存在若干个点入度都为0,因此在拓扑排序的题型中一般还会有其他的限制条件。这样一般是从大到小或从小到大取,并且采用小顶堆或者大顶堆来形成最终的顺序。

经典题目

HDU 5695 Gym Class

题意

思路

代码
同上面的,因为前面的要尽可能大,所以使用大顶堆。toposort里面遍历0入度的点应当从大到小。
这条题目注意最后的方案要lld输出。

HDU 4857 逃生

题意

现在需要对[1..n]排序,要求编号小的一定在编号大的前面,但是此外还有若干形如(a, b)的约束条件,要求a必须在b前面。现在输出排序方案(保证一定有解)。

正确的思路

代码
需要反向拓扑(反向建边),维护一个大顶堆,然后反向输出

错误的思路

代码
读取(a, b),对(a, b)建立有向边(正向拓扑),维护小顶堆,正序输出。

错误原因

在阅读了这个帖子之后,明白了。
考虑下面的例子:

1
3 1
3 1

正确的输出应当是

3 1 2

但是我的程序输出了

2 3 1

按照题意,3应该在1前面,1应该在2前面。但我的实现保证了按字典序排列,2的字典序较小,所以排在3前面,但是这就不满足编号小的在编号大的前面这个限制条件了。