> 拓扑排序（Topological sorting）要解决的问题是如何给一个有向无环图的所有节点排序．
> OI-wiki
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前置芝士： BFS 邻接表
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
定义：
有向无环图 (DAG\mathtt{DAG}DAG)：
顾名思义，该图边有向且无环。
其性质为能拓扑排序的图和 DAG\mathtt{DAG}DAG 是成对应关系的。
即一 DAG\mathtt{DAG}DAG 必然能进行拓扑排序，反之亦然。
拓扑排序，是指将图中的顶点以线性方式进行排序，使得对于任何的顶点 uuu 到 vvv 的有向边 (u,v)(u, v)(u,v), 都可以有 uuu 在 vvv 的前面．
一个 DAG\mathtt{DAG}DAG 的拓扑序不一定唯一。
例：
对于该图，可能的拓扑序为 123456123456123456, 132456132456132456 等。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
构造拓扑序列步骤
从图中选择一个入度为 000 的点。
记录该顶点，从图中删除此顶点及其所有的出边，统计入度。
重复上面两步，直到所有顶点都被记录，拓扑排序完成。
若图中不存在入度为零的点但仍有点未被记录，此时说明图是有环图，拓扑排序无法完成。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
实现：
一般采用 Kahn\mathtt{Kahn}Kahn
初始状态下，集合 SSS 装着所有入度为 000 的点，ansansans 是一个空列表。
每次从 SSS 中取出一个点 uuu（可以随便取）放入 ansansans, 然后将 uuu 的所有边 (u,v1),(u,v2),(u,v3)⋯(u, v_1), (u, v_2), (u, v_3) \cdots(u,v1 ),(u,v2 ),(u,v3 )⋯ 删除。
对于边 (u,v)(u, v)(u,v)，若将该边删除后点 vvv 的入度变为 000，则将 vvv 放入 SSS 中．
不断重复以上过程，直到集合 SSS 为空．检查图中是否存在任何边，如果有，那么这个图一定有环。
否则 ansansans 中顶点的顺序就是构造拓扑序列的结果．
模板：
此时若 ansansans 存储了所有节点，则原图为有向无环图。
否则原图有环。
此实现方式 时间复杂度 O(V+E)O(V + E)O(V+E)，若使用优先队列，时间复杂度变为 O(VlogV+E)O(V \log V + E)O(VlogV+E)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题
A29810
大意：
给定一图，若其为 DAG\mathtt{DAG}DAG 输出拓扑序列，反之输出 has circle.
一道板子，注意输出格式。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
拓扑排序亦可以和 DP 结合。
例题：
A85523
大意：给定一图，对于一边 (u,v)(u, v)(u,v) 动物 uuu 可以吃掉动物 vvv。
求最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者这样的链的总数，对 801120028011200280112002 取模。
思路：
因为要一端是生产者，故要记录出度。
同时，若对于一点 uuu 能直接连接到 vvv 则进行累加，将每一点在拓扑排序时增加所有上级的即可。
最后统计出度为零的点的方案总数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题：
A226
大意：
有 nnn 个点，每个点有一个点权。
有 mmm 个序列，并且满足要求：若包含点 uuu，则序列内所有点的点权都大于等于 uuu 的点权。
求最大点权的最小值。
思路：
考虑序列中的相邻点 aia_iai 和 ai+1a_{i+1}ai+1 ：
它们之间的站点 ai+1,ai+2,…,ai+1−1a_i+1, a_i+2, \dots, a_{i+1}-1ai +1,ai +2,…,ai+1 −1 都是未停靠的。
对于中间任一未停靠站 jjj
jjj 的点权必然小于 aia_iai ，否则 jjj 必须加入序列。
随后在拓扑时记录答案数组即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
P1113
有 n 个任务，编号 1,2,…,n1,2,…,n1,2,…,n。
每个任务都有完成所需的时间。
任务之间有依赖关系：某些任务必须先于另一些任务完成。
可以同时做任意个任务。
求所有任务完成的最短时间。
思路：
等一下写（
