最短路径树（SPT问题）定义：在一张无向带权联通图中，有这样一棵生成树：满足从根节点到任意点的路径都为原图中根到任意点的最短路径。 性质：记根节点 \(Root\) 到某一结点 \(x\) 的最短距离 \(dis_{Root,x}\) ，在…

欧拉路径/欧拉回路 Hierholzers欧拉路径：一笔画完图中全部边，画的顺序就是一个可行解；当起点终点相同时称欧拉回路。有向图欧拉路径存在判定 有向图欧拉路径存在：\(\tt ^1\) 恰有一个点出度比入度多 \(1\) （为起点…

无源汇点的最小割问题 Stoer–Wagner也称为全局最小割。定义补充（与《网络流》中的定义不同）： 割：是一个边集，去掉其中所有边能使一张网络流图不再连通（即分成两个子图）。通过递归的方式来解决无向正权图上的全…

染色法判定二分图 (dfs算法) 判断一张图能否被二分染色。 vector<int> vis(n + 1); auto dfs = [&](auto self, int x, int type) -> void {vis[x] = type;for (auto y : ver[x]) {if (vis[y] == type) {…

链式前向星建图与搜索 很少使用这种建图法。\(\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\) ，可以不需再…