图论

最小生成树

Kruskal算法:用并查集维护集合之间的联通性,将所有边从小到大排序,每次取两点不在同一联通分量的边加入最小生成树,直到所有的节点联通。

正确性证明:假设边e连接两个联通分量i和j,若不选e,则一定有另外一条边连接i和j,这条边的长度一定小于e的长度,所得的生成树一定比加入边e所得的生成树大,所以最小生成树中一定包含连接i和j边权最小的边e。

Prim算法:从一个点开始,每次寻找与该点相邻距离最小的边加入最小生成树中,保证每个点只访问一次。

强联通分量分解

首先DFS一遍,对每个节点的访问次序标号,将所有边反向,按标号从后往前依次进行DFS,每一次DFS访问到的所有点组成一个联通分量。

最近公共祖先

从树根开始遍历每个点,记下该树的DFS序和每个节点第一次被访问在DFS序中的位置。用稀疏表维护对应DFS序上每个点的深度,每次查询只要求出两点第一次在DFS序中出现位置之间的深度最小值对应的节点编号即可。

树链剖分

第一次DFS将无根树转化为有根树,同时统计每个节点对应子树的节点个数,得到每个节点的重子节点(总子节点个数最多的节点)。

第二次DFS将所有节点按重子节点优先的顺序重新标号,记录每条重链的链头。

最后用线段树维护重新标号后的数列。