最小树形图（朱刘算法）树形图：有向图中无环，每个点的入度为1（根节点除外）的图 最小树形图：边权和最小的树形图，可以认为是有向图的最小生成树 朱刘算法步骤： 对于每个点（除了根节点），找出所有入边中权值最小的边 判断选出的边中是否存在环。若不存在环...

无向图的双连通分量边双连通分量(e-DCC)桥：若被删去，则其相连的两个部分不连通 边双连通分量：极大的不包含桥的连通块 如何找到桥 若dfn[x]<low[y]，则边(x,y)是桥（即y无论如何都走不到x） 如何找所有边的双连通分量 方法...

斯特林数第一类斯特林数将 $1 \sim n$ 划分为 $k$ 个圆排列的方案数，记作 $s(n,k)$ 或 $\begin{bmatrix} n\ k\end{bmatrix}$ 求法： $\begin{bmatrix} n\ k\end{bma...

整数二分本质:可以使区间被分为两部分，其中一部分满足性质A,另一部分不满足性质A，即可使用二分 模板一:取左部分的右端点 1234567mid=(l+r+1)>>1;//若mid=l+r>>1，则当l=r-1时，mid=l，此...

数据结构目录树状数组$lowbit(x)$：$x$二进制下第一个1 123int lowbit(x){ return x&-x;} 支配区间：$[i-lowbit(i)+1,i]$ 引理1：对于任意x,y，其支配区...

搜索深度优先搜索($DFS$)，广度优先搜索($BFS$) 对比： 数据结构 空间 $DFS$ $stack$ $O(h)$ 不具最短性 $BFS$ $queue$ $O(2^h)$ 最短路 $DFS$:例1：给定一个数字$...

拓扑排序定义：若一个由图中所有点构成的序列 $A$ 满足：对于图中的每条边 $(x,y)$，$x$ 在 $A$ 中都出现在 $y$ 之前，则称 $A$ 是该图的一个拓扑序列。 拓扑序列只存在于有向图中，可以证明，所有的有向无环图($DAG$)都一定有...

快速排序思想：分治 步骤 确定分界点 选择一个点（ $a[l],a[r],a[mid]…$）,记为$x$ 调整范围 令所有$\le x$ 的数在$x$左侧，$>x$ 的数在 $x$ 右侧 递归处理左右两段 重复处理$[1 \thicks...

快速傅里叶变换（FFT）快速傅里叶变换用于解决多项式乘法（卷积）问题 给定一个 $ n $ 次多项式 $ F(x) = a_0 + a_1x + a_2x^2+…+a_nx^n $。 以及一个 $ m $ 次多项式 $ G(x) =...

归并排序流程： 确定分界点 一般取$mid=l+r>>1$ 递归两侧 $[l\thicksim mid],[mid+1 \thicksim r]$ 合并两侧的序列 每次比较两侧的第一个数，取较小值 代码实现（$O(n\...