并查集
设 m 为合并次数,n 为点数,则:
- 朴素:O(mn)
- 按 size / height 合并:O(mlogn)
- 路径压缩:O(mlogn)
- 按 size / height 合并 + 路径压缩:近似 O(m)
最小生成树 MST
Boruvka
每一轮,对每个联通块选择一条到其他联通块的一条最短路径。
时间复杂度 O((n+m)logn)。
最近公共祖先 LCA
倍增 & 树剖
时间复杂度 O((n+q)logn)。
Tarjan
只能离线。
时间复杂度 O(n+q)。
欧拉序 + ST 表
时间复杂度 O(nlogn+q),但是有 2 倍常数,实际也不会很快。
DFS 序 + ST 表
讨论一组询问 u,v 和他们的 lca 的 DFS 序的关系。假定 dfn(u)≤dfn(v)。
- 如果 u 是 v 的祖先或 u=v,直接返回 u 即可。
- 否则,DFS 序上 u 到 v 间 dep 最小的点一定是 lca 的儿子。
实现时,较为简单的写法是:
- 判断 u 和 v 是否相等。若是,直接返回。
- 若 dfn(u)>dfn(v),交换 u,v。
- 在 ST 表上查得 [dfn(u)+1,dfn(v)] 中 dep 最小的点 d,返回 father(d)。
时间复杂度 O(nlogn+q),常数更小,实际表现更快。
LCT
先 makeRoot(root),再 access(x),最后 access(y) 时的最后一条虚边即为 LCA。
支持加边、删边、换根。
时间复杂度 O((n+q)logn)。
树的直径、中心和重心
树的直径
求解方法:两次搜索,或 DP。
性质:
- 两次搜索求解时用到的性质:树上一点离它最远的点一定是直径一个端点。要求边权非负。
- DP 求解时用到的性质:直径一定是直径所有点 LCA 的子树内最长链和次长链的并。不要求边权非负。
- 合并两棵树(或两点集) T1,T2 形成新树 T,则 T 的直径的两个端点,一定是 T1 直径两端点和 T2 直径两端点四个中的两个。要求边权非负。
![](/img/loading.gif)
如图,合并蓝色点集与红色点集,原直径为 (A,B) 和 (F,G),新直径为 (E,G)。
树的中心
性质:
- 一棵树最多有两个中心且相邻,它们是直径的中点。
- 树的中心是树的所有点中到其它点距离最大值最小的。
树的重心
性质:
- 删除重心后所得的所有子树中,节点数不超过原树的 21。
- 一棵树最多有两个重心,且相邻。
- 树中所有点到某个点的距离和中,到重心的距离和是最小的;如果这棵树有两个重心,那么他们的距离和一样。
- 把两棵树通过一条边相连,新的树的重心在原来两棵树重心的连线上。
- 一棵树添加或者删除一个节点,树的重心最多只移动一条边的位置。
- 一棵树的重心,一定在根节点所在的重链上。
树上路径相关
判断点 u 是否在路径 (x,y) 上:
- dis(x,u)+dis(u,y)=dis(x,y)。
判断两条路径 (u,v) 和 (x,y) 是否相交(下面假设 dep(lca(u,v))≥dep(lca(x,y)) ):
- 当 lca(u,v) 在路径 (x,y) 上时,两条路径相交。
- 在 lca(u,x),lca(u,y),lca(v,x),lca(v,y) 四个点中,记深度最大和次大的两个点分别为 p0 和 p1,则当 p0=p1 且 dep(p0)<dep(lca(x,y))(深度小于任意一条路径的 LCA)时,两条路径不交。
求两条相交路径 (u,v) 和 (x,y) 的相交部分:
- 在 lca(u,x),lca(u,y),lca(v,x),lca(v,y) 四个点中,记深度最大和次大的两个点分别为 p0 和 p1,则相交部分为 (p0,p1)。
拓扑排序
有向无环图是有拓扑序的充要条件。
- 在有向无环图中一定能找到至少一个入度为 0 的点。
反证法:所有点入度不为 0 则一定有环。
- 删除入度为 0 的点后,剩下的图要么为空,要么仍然是有向无环图。重复此操作直到图为空。
- 删点顺序为一个拓扑序。
最短路算法
Floyd
fu,v,k=min{fu,v,k−1,fu,k,k−1+fk,v,k−1}
若 fi,i,n<0 则存在负环。
时间复杂度 O(n3)。作用于稠密图全源最短路。
Bellman-Ford
fi,k=min{fi,k−1,(j,i)∈Emin{fj,k−1+wj,i}}
若 fi,n<fi,n−1 则存在负环。但若负环都不与源点联通,则不存在 fi,n<fi,n−1 。
时间复杂度 O(nm)。
SPFA
卡 SPFA 及其优化简易方法:
- 生成一棵以起点为根的树,树高尽量高。比如 1 为起点时,可以令每个点 i 的父亲在 max{i−5,1}∼i−1 随机,边权随机,作为最短路径树,同时直接递推求出每个点的带权深度 di。
- 对于剩下的边,端点 (u,v) 随机,边权在 ∣du−dv∣ 到 ∣du−dv∣+5 随机。如果是有向图则去掉绝对值符号;5 可以换成其他较小的正数。这样生成的图中,次短路的条数非常的多,而 SPFA 一旦错误地进入了次短路的分支,就会使得一整棵子树被赋错误的距离,从而在后期不得不重新更新。而由于边权接近,剪枝的效果会受到很大影响。
原文链接:如何卡 SPFA 。
Dijkstra
朴素时间复杂度 O(n2)。堆(优先队列)优化时间复杂度 O((n+m)logm),稠密图时间复杂度 O(n2logn)。斐波那契堆优化时间复杂度 O(nlogn+m)。
入堆次数 >n 则有负环。
Johnson
边权改为 wu,v+du−dv,其中 di 是常数,它在 Johnson 中被设为 SPFA 从超级源点(新建虚拟节点向每个点连 0 边)到 i 的距离。
时间复杂度 O(nmlogm)。作用于稀疏图全源最短路。
图的连通性 & Tarjan
点双连通分量
注意把边入栈,入栈条件为:不在栈中,且不在任意点双中。
2-SAT 问题
建图:对于给出的条件「x∨y=1」,连边 ¬x→y 和 ¬y→x。
构造方案:
- 按照逆拓扑序决策,即一个变量的取值为所在连通块拓扑序较大者。
- 逆拓扑序即找到强连通分量的顺序。
- 两种取值均可,当且仅当拓扑序小者无法找到拓扑序大者。
建模套路:
- x 必选 ⇒x∨x=1。
- 整数等式:x=2⇒(x≥2)∧¬(x≥3)。
- 前缀和优化,把两排点变成四排点(ai,¬ai,si,¬si)。
Prufer 序列(Prüfer)
Prufer 序列可以将一个带标号 n 个结点的树用 n−2 个 1∼n 的整数表示。据此,n 个点有标号无根树的个数为 nn−2,n 个点有标号有根树的个数为 nn−1。
性质:
- 在构造完 Prufer 序列后原树中会剩下两个结点,其中一个一定是编号最大的点 n。
- 每个结点在序列中出现的次数是其度数减 1。叶子结点在 Prufer 序列中不出现。
- 随机生成一个 Prufer 序列,树高的期望是 O(n) 的。
求无根树的 Prufer 序列
每次选择编号最小的叶子删除,并在序列中添加其父亲节点。用堆做到 O(nlogn)。
根据 Prufer 序列建立原树
将不在 Prufer 序列里的点加入 S 集合。每次:
- 找到 S 集合中编号最小的点,使它认当前 Prufer 序列中的第一个点为父亲。
- 若父亲在 Prufer 序列中被删空,则将其加入 S 集合。
- 重复上述过程。
最后将 S 中剩余的两个元素相连。
时间复杂度 O(nlogn)。
凯莱定理(Cayley)
n 阶完全图有 nn−2 棵生成树。
广义凯莱定理(Ex Cayley)[UNFINISHED]
n 个点 k 棵树的有标号森林,满足给定的 k 个点不连通的个数为 k⋅nn−k−1。
证明:先把钦定的 k 个点当做根,将它们与虚拟节点 0 连边。这棵树的 prufer 序列长为 n−1,而其中 k 个是 0,其它 n−k−1 个是 1∼n。方案数就是 $$(?)
加边成树方案数
给你一个无环的无向图,求加边方案数,把无向图变成树。
设连通分量共 c 个,其大小分别为 k1,k2,⋯,kc。答案为 (i=1∑cki)c−2⋅i=1∏cki。
平面图 & 对偶图
平面图欧拉公式
连通平面图中,有:n−m−r=2。其中 n 为平面图点数,m 为边数,r 为面数(被边分割出的区块数)。
推广:任意平面图中,有:n−m−r=k+1。其中 k 为(点的)连通块个数。
推论:平面图 m≤3n−6。
平面图的对偶图
- 平面图最小割等于对偶图最小环。删除边 S−T 后等同于最短路。
- 平面图边数等于对偶图边数,平面图面数等于对偶图点数。