- tarjan 算法
- 虚树
- DAG 剖分
- 矩阵树定理
- 最小树形图 （ ）
- 斯坦纳树 （感觉可以看看？）
- 同余最短路
- 平面图 and 对偶图
- 线性规划
- 网络流
- 一般图最大匹配
- Prüfer 序列
- 竞赛图
- 稳定婚姻问题
- 2-sat
- 仙人掌
- Dilworth 定理 （ ）
tarjan 算法
有向图 \(\to\) 强连通分量
无向图 \(\to\) 广义圆方树
一些性质：
- 点双中任意两个点之间都存在至少两条不相交的路径 （除去起点和终点）。
虚树
关于虚树的几种方法：
- 求虚树的点数 （点数） \(\to\) 每两个点的 $\operatorname {lca} $ 所构成的集合大小
- 求虚树的边数：
- 按照 dfs 序排序之后相邻两项的距离之和（包括第一项和最后一项）再除以 \(2\)。
- 子树中至少包含一个点的点数减去 \(lca\) 的祖先个数。
DAG 剖分
要求总路径数不是很大 （一般配合 SAM 求第 \(k\) 大字串）。
每个点指向路径数最大的一条边，称为重边，这样一条路径最多跳 \(\log\) 条轻边。
可以用倍增做到 $\log ^2 $ 。类似的情况可以使用可持久化平衡树。保证合并复杂度 \(O(\log)\)。