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

每个顶点出现且只出现一次；
若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前面，但是这就不满足编号小的在编号大的前面这个限制条件了。