图论部分(2025.6.25)

· · 个人记录

注意

在考试时注意时间，用基本技巧（倍增，dfs序，树上差分）解决的问题就不要使用高级数据结构（树链剖分，线段树合并和dsu on tree）

倍增维护信息时要注意lca周围

幂等信息

一个信息是幂等的，就是说这个信息在合并后任是自己，比如最大值算多了答案、仍然正确

这样就可以把信息合并次数减少，比如将一条链拆分成 2^k 长的部分，这样就只用 O(1) 的时间来合并

树上差分技巧

可将加链转化为两点的加，最后到根一次算出来

最小生成树

有 Prim (每次扩展权值最小的边) , Kruskal (边从小到大排序), Boruvka （每次找一个点或连通块，在所有出边中找一个权值最小的出边）（思想非常重要）。

生成树相关构造与 dfs 树

对于无向图，dfs 树具有不存在横叉边的性质。

推论：dfs 树附带了若干个独立集：叶子是独立集，同深度的点是独立集。

最小生成树具有可合并性。特别地，如果涉及到的点很少，甚至可以建虚树来合并。合并时只用合并少量两边的点，不用合并所有的点。

点双联通分量与圆方树

略

2-sat

注意 2-sat 只能解决布尔方程组，所以要将其他的限制转化为布尔方程组，常将变量 x_{i,j} 设为 a_i \le j 为真或假，然后进行表示

欧拉回路

注意，必须在回溯时进行边的加入，否则会错

欧拉回路有两个性质：

  1. 环覆盖性，即图上的所有点都会被环覆盖
  2. 入度等于出度