并查集

设 $m$ 为合并次数， $n$ 为点数，则：

朴素： $O(mn)$
按 size / height 合并： $O(m\log n)$
路径压缩： $O(m\log n)$
按 size / height 合并 + 路径压缩：近似 $O(m)$

最小生成树 MST

Boruvka

每一轮，对每个联通块选择一条到其他联通块的一条最短路径。

时间复杂度 $O((n+m)\log n)$ 。

最近公共祖先 LCA

倍增 & 树剖

时间复杂度 $O((n+q)\log n)$ 。

Tarjan

只能离线。

时间复杂度 $O(n+q)$ 。

欧拉序 + ST 表

时间复杂度 $O(n\log n+q)$ ，但是有 $2$ 倍常数，实际也不会很快。

DFS 序 + ST 表

讨论一组询问 $u,v$ 和他们的 $\text{lca}$ 的 DFS 序的关系。假定 $\text{dfn}(u)\le\text{dfn}(v)$ 。

如果 $u$ 是 $v$ 的祖先或 $u=v$ ，直接返回 $u$ 即可。
否则，DFS 序上 $u$ 到 $v$ 间 $\text{dep}$ 最小的点一定是 $\text{lca}$ 的儿子。

实现时，较为简单的写法是：

判断 $u$ 和 $v$ 是否相等。若是，直接返回。
若 $\text{dfn}(u)>\text{dfn}(v)$ ，交换 $u,v$ 。
在 ST 表上查得 $[\text{dfn}(u)+1,\text{dfn}(v)]$ 中 $\text{dep}$ 最小的点 $d$ ，返回 $\text{father}(d)$ 。

时间复杂度 $O(n\log n+q)$ ，常数更小，实际表现更快。

LCT

先 $\text{makeRoot}(\text{root})$ ，再 $\text{access}(x)$ ，最后 $\text{access}(y)$ 时的最后一条虚边即为 LCA。

支持加边、删边、换根。

时间复杂度 $O((n+q)\log n)$ 。

树的直径、中心和重心

树的直径

求解方法：两次搜索，或 DP。

性质：

两次搜索求解时用到的性质：树上一点离它最远的点一定是直径一个端点。要求边权非负。
DP 求解时用到的性质：直径一定是直径所有点 LCA 的子树内最长链和次长链的并。不要求边权非负。
合并两棵树（或两点集） $T_1,T_2$ 形成新树 $T$ ，则 $T$ 的直径的两个端点，一定是 $T_1$ 直径两端点和 $T_2$ 直径两端点四个中的两个。要求边权非负。

如图，合并蓝色点集与红色点集，原直径为 $(A,B)$ 和 $(F,G)$ ，新直径为 $(E,G)$ 。

树的中心

性质：

一棵树最多有两个中心且相邻，它们是直径的中点。
树的中心是树的所有点中到其它点距离最大值最小的。

树的重心

性质：

删除重心后所得的所有子树中，节点数不超过原树的 $\frac12$ 。
一棵树最多有两个重心，且相邻。
树中所有点到某个点的距离和中，到重心的距离和是最小的；如果这棵树有两个重心，那么他们的距离和一样。
把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。
一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。
一棵树的重心，一定在根节点所在的重链上。

树上路径相关

判断点 $u$ 是否在路径 $(x,y)$ 上：

$\text{dis}(x,u)+\text{dis}(u,y)=\text{dis}(x,y)$ 。

判断两条路径 $(u,v)$ 和 $(x,y)$ 是否相交（下面假设 $\text{dep}(\text{lca}(u,v))\ge\text{dep}(\text{lca}(x,y))$ ）：

当 $\text{lca}(u,v)$ 在路径 $(x,y)$ 上时，两条路径相交。
在 $\text{lca}(u,x),\text{lca}(u,y),\text{lca}(v,x),\text{lca}(v,y)$ 四个点中，记深度最大和次大的两个点分别为 $p_0$ 和 $p_1$ ，则当 $p_0=p_1$ 且 $\text{dep}(p_0)<\text{dep}(\text{lca}(x,y))$ （深度小于任意一条路径的 LCA）时，两条路径不交。

求两条相交路径 $(u,v)$ 和 $(x,y)$ 的相交部分：

在 $\text{lca}(u,x),\text{lca}(u,y),\text{lca}(v,x),\text{lca}(v,y)$ 四个点中，记深度最大和次大的两个点分别为 $p_0$ 和 $p_1$ ，则相交部分为 $(p_0,p_1)$ 。

拓扑排序

有向无环图是有拓扑序的充要条件。

在有向无环图中一定能找到至少一个入度为 $0$ 的点。
反证法：所有点入度不为 $0$ 则一定有环。

删除入度为 $0$ 的点后，剩下的图要么为空，要么仍然是有向无环图。重复此操作直到图为空。

删点顺序为一个拓扑序。

最短路算法

Floyd

f_{u,v,k}=\min\{f_{u,v,k-1},f_{u,k,k-1}+f_{k,v,k-1}\}

若 $f_{i,i,n}<0$ 则存在负环。

时间复杂度 $O(n^3)$ 。作用于稠密图全源最短路。

Bellman-Ford

f_{i,k}=\min\left\{f_{i,k-1},\min_{(j,i)\in E}\{f_{j,k-1}+w_{j,i}\}\right\}

若 $f_{i,n}<f_{i,n-1}$ 则存在负环。但若负环都不与源点联通，则不存在 $f_{i,n}<f_{i,n-1}$ 。

时间复杂度 $O(nm)$ 。

SPFA

卡 SPFA 及其优化简易方法：

生成一棵以起点为根的树，树高尽量高。比如 $1$ 为起点时，可以令每个点 $i$ 的父亲在 $\max\{i−5,1\}\sim i−1$ 随机，边权随机，作为最短路径树，同时直接递推求出每个点的带权深度 $d_i$ 。
对于剩下的边，端点 $(u,v)$ 随机，边权在 $|d_u−d_v|$ 到 $|d_u−d_v|+5$ 随机。如果是有向图则去掉绝对值符号； $5$ 可以换成其他较小的正数。这样生成的图中，次短路的条数非常的多，而 SPFA 一旦错误地进入了次短路的分支，就会使得一整棵子树被赋错误的距离，从而在后期不得不重新更新。而由于边权接近，剪枝的效果会受到很大影响。

原文链接：如何卡 SPFA 。

Dijkstra

朴素时间复杂度 $O(n^2)$ 。堆（优先队列）优化时间复杂度 $O((n+m)\log m)$ ，稠密图时间复杂度 $O(n^2\log n)$ 。斐波那契堆优化时间复杂度 $O(n\log n+m)$ 。

入堆次数 $>n$ 则有负环。

Johnson

边权改为 $w_{u,v}+d_u-d_v$ ，其中 ${d_i}$ 是常数，它在 Johnson 中被设为 SPFA 从超级源点（新建虚拟节点向每个点连 $0$ 边）到 $i$ 的距离。

时间复杂度 $O(nm\log m)$ 。作用于稀疏图全源最短路。

图的连通性 & Tarjan

点双连通分量

注意把边入栈，入栈条件为：不在栈中，且不在任意点双中。

2-SAT 问题

建图：对于给出的条件「 $x\lor y=1$ 」，连边 $\neg x\rightarrow y$ 和 $\neg y\rightarrow x$ 。

构造方案：

按照逆拓扑序决策，即一个变量的取值为所在连通块拓扑序较大者。
逆拓扑序即找到强连通分量的顺序。
两种取值均可，当且仅当拓扑序小者无法找到拓扑序大者。

建模套路：

$x$ 必选 $\Rightarrow x\lor x=1$ 。
整数等式： $x=2\Rightarrow (x\ge2)\land\neg(x\ge3)$ 。
前缀和优化，把两排点变成四排点（ $a_i,\neg a_i,s_i,\neg s_i$ ）。

Prufer 序列（Prüfer）

Prufer 序列可以将一个带标号 $n$ 个结点的树用 $n-2$ 个 $1\sim n$ 的整数表示。据此， $n$ 个点有标号无根树的个数为 $n^{n-2}$ ， $n$ 个点有标号有根树的个数为 $n^{n-1}$ 。

性质：

在构造完 Prufer 序列后原树中会剩下两个结点，其中一个一定是编号最大的点 $n$ 。
每个结点在序列中出现的次数是其度数减 $1$ 。叶子结点在 Prufer 序列中不出现。
随机生成一个 Prufer 序列，树高的期望是 $O(\sqrt n)$ 的。

求无根树的 Prufer 序列

每次选择编号最小的叶子删除，并在序列中添加其父亲节点。用堆做到 $O(n\log n)$ 。

根据 Prufer 序列建立原树

将不在 Prufer 序列里的点加入 $S$ 集合。每次：

找到 $S$ 集合中编号最小的点，使它认当前 Prufer 序列中的第一个点为父亲。
若父亲在 Prufer 序列中被删空，则将其加入 $S$ 集合。
重复上述过程。

最后将 $S$ 中剩余的两个元素相连。

时间复杂度 $O(n\log n)$ 。

凯莱定理（Cayley）

$n$ 阶完全图有 $n^{n-2}$ 棵生成树。

广义凯莱定理（Ex Cayley）[UNFINISHED]

$n$ 个点 $k$ 棵树的有标号森林，满足给定的 $k$ 个点不连通的个数为 $k\cdot n^{n-k-1}$ 。

证明：先把钦定的 $k$ 个点当做根，将它们与虚拟节点 $0$ 连边。这棵树的 prufer 序列长为 $n-1$ ，而其中 $k$ 个是 $0$ ，其它 $n-k-1$ 个是 $1\sim n$ 。方案数就是 $$（？）

加边成树方案数

给你一个无环的无向图，求加边方案数，把无向图变成树。

设连通分量共 $c$ 个，其大小分别为 $k_1,k_2,\cdots,k_c$ 。答案为 $\left(\sum\limits_ {i=1}^c k_i\right)^{c-2}\cdot\prod\limits_{i=1}^c k_i$ 。

平面图 & 对偶图

平面图欧拉公式

连通平面图中，有： $n-m-r=2$ 。其中 $n$ 为平面图点数， $m$ 为边数， $r$ 为面数（被边分割出的区块数）。

推广：任意平面图中，有： $n-m-r=k+1$ 。其中 $k$ 为（点的）连通块个数。

推论：平面图 $m\le3n-6$ 。

平面图的对偶图

平面图最小割等于对偶图最小环。删除边 $S-T$ 后等同于最短路。
平面图边数等于对偶图边数，平面图面数等于对偶图点数。