拓扑排序

拓扑排序真是个好东西。

1、它可以判断是不是有向无环图;(如果做完拓扑排序,还有点的度数不为0,那么一定有环)

2、在优先队列上跑拓扑排序,能够得到字典序最小的一组拓扑序,也就是满足限制条件的字典序最小的解(将限制条件转成边)

3、假使你有一堆已知左右端点的边,你想把他们连成一条最长链,甚至你还想知道这条最长链的每一个节点。(在拓扑排序时顺便dp,和记录就行)

4、留坑。


发表于 2018-09-17 14:43:35 in 知识点