一、拓扑排序

有多个形如$x_i < x_j$的不等式,求这些不等式是否有解,并求出可能的大小关系。
把不等关系看成有向边,建图,从入度为$0$的所有点开始做一次多源BFS。需要注意的是每次只能将已出队的点移除后入度为$0$的点入队
当图中不存在环时,不等式组有解。反之,不等式组无解。这些点的出队顺序就是可能的大小关系,即图的拓扑序。显然,只有有向无环图才有拓扑序。

1、LCA(倍增法)

不知道倍增是个啥的同志们可以先看看这题
$LCA$的倍增求法和$ST$表一样,都是需要先进行一次$O(N\log N)$的预处理。只是求$LCA$的时间复杂度是$O(\log N)$,和$ST$表不同。这也不难理解,$ST$表是在区间(链)上的,而求$LCA$是在树上的,不能通过简单代数加减求得。
倍增求$LCA$有两步预处理,分别是一次$DFS$(弄清楚各个点的父节点以及深度),和一次递推计算(感觉像$DP$一样。)

这几天学DP学得有一定的心得,便来写一发学习笔记。知道自己get到的只不过是DP的一点点皮毛,所以希望自己以后能学习到更多的有用的知识。

星期二上课时教练说要讲DFS,当时就在想:DFS上个学期不是讲函数递归时不就讲过了吗???为什么还要再讲一遍?
认认真真地学了,写了5,6个小时的DFS(由于我们都是蒟蒻,没有学剪枝,因此写不了过难的题),看看天,要下雨了。难道今天就要把时间全耗在简单DFS上,一点提升都没有了吗?