链式前向星建图与搜索 很少使用这种建图法。\(\tt dfs\) ：标准复杂度为 \(\mathcal O(N+M)\)。节点子节点的数量包含它自己（至少为 \(1\)），深度从 \(0\) 开始（根节点深度为 \(0\)）。\(\tt bfs\) ：深度从 \(1\) …

一般图最大匹配（带花树算法） 与二分图匹配的差别在于图中可能存在奇环，时间复杂度与边的数量无关，为 \(\mathcal O(N^3)\) 。下方模板编号从 \(0\) 开始，例题为 UOJ #79. 一般图最大匹配 。 struct Graph {int n;…

有一棵以 \(1\) 为根， \(n\) 个节点的树，每个节点有一个颜色白/黑。给定 \(q\) 组询问，每组询问给了一个 \(u\)，表示将 \(u\) 子树内的点的颜色全部翻转。每次操作后回答至少需要几条从根开始的链才能覆盖所有黑点…

缩点（Tarjan 算法） （有向图）强连通分量缩点 强连通分量缩点后的图称为 SCC。以 \(\mathcal O (N + M)\) 的复杂度完成上述全部操作。性质：缩点后的图拥有拓扑序 \(color_{cnt}, color_{cnt-1},…,1\) ，可以不需再…

平面图最短路（对偶图） 对于矩阵图，建立对偶图的过程如下（注释部分为建立原图），其中数据的给出顺序依次为：各 \(n(n+1)\) 个数字分别代表从左向右、从上向下、从右向左、从下向上的边。 for (int i = 1; i <=…

多源汇最短路（APSP问题） 使用邻接矩阵存图，可以处理负权边，以 \(\mathcal{O}(N^3)\) 的复杂度计算。注意，这里建立的是单向边，计算双向边需要额外加边。 const int N = 210; int n, m, d[N][N];void floyd() {fo…

最小生成树（MST问题） （稀疏图）Prim算法 使用邻接矩阵存图，以 \(\mathcal{O}(N^2+M)\) 的复杂度计算，思想与 \(\tt djikstra\) 基本一致。 const int N = 550, INF = 0x3f3f3f3f; int n, m, g[N][N]; int d[N], v…

常见概念oriented graph：有向图 bidirectional edges：双向边平面图：若能将无向图 \(G=(V,E)\) 画在平面上使得任意两条无重合顶点的边不相交，则称 \(G\) 是平面图。 无向正权图上某一点的偏心距：记为 \(ecc(u) = …