图论
拓扑排序
定义
拓扑排序要解决的问题是给一个有向无环图的所有节点排序。
合理性证明
考虑一个图，删掉某个入度为0的节点之后，如果新图可以拓扑排序，那么原图一定也可以。反过来，如果原图可以拓扑排序，那么删掉后也可以。
应用
拓扑排序可以判断图中是否有环，还可以用来判断图是否是一条链。
Tarjan
定义
有向图的 DFS 生成树主要有 4 种边：
1.树边（tree edge）：每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
2.反祖边（back edge）：也被叫做回边，即指向祖先结点的边。
3.横叉边（cross edge）：它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。
4.前向边（forward edge）：它是在搜索的时候遇到子树中的结点的时候形成的。
强连通分量
用Tarjan算法来求强连通分量，原理是DFS，复杂度O(n+m)。
用栈来维护搜索树。
如果(u,v)是搜索树上的边（第一次访问v），low(u)=min(low(u),low(v))
如果(u,v)从u指向其在搜索树上的祖先v，low(u)=min(low(u),dfn(v))（v显然在栈中）
如果(u,v)从u指向搜索树上另一棵子树中的v，且v还在栈中，low(u)=min(low(u),dfn(v))
割点割边
割点：对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点。
我们判断某个点是否是割点的根据是：对于某个顶点 u，如果存在至少一个顶点v（u 的儿子），使得low(v) >= dfn(u) ，即不能回到祖先，那么 
点为割点。
此根据惟独不适用于搜索的起始点，其需要特殊考虑：若该点不是割点，则其他路径亦能到达全部结点，因此从起始点只「向下搜了一次」，即在搜索树内仅有一个子结点。如果在搜索树内有两个及以上的儿子，那么他一定是割点了
割边：对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。
和割点差不多，只要改一处: low(v) > dfn(u) 就可以了，而且不需要考虑根节点的问题。
最短路
Dijkstra
SPFA
由于每次入队dis(v)都会变小，dis不会无限小，所以这种方法可以求出最短路如果一个点n次入队，说明存在负环。
Floyd(区间DP)
可以求出多源最短路。
生成树
最小瓶颈路
定义
无向图中 x 到 y 的最小瓶颈路是这样的一类简单路径，满足这条路径上的最大的边权在所有 x 到 y 的简单路径中是最小的。
Kruskal 重构树
定义
在跑 Kruskal 的过程中我们会从小到大加入若干条边。现在我们仍然按照这个顺序。
首先新建n个集合，每个集合恰有一个节点，点权为0。
每一次加边会合并两个集合，我们可以新建一个点，点权为加入边的边权，同时将两个集合的根节点分别设为新建点的左儿子和右儿子。然后我们将两个集合和新建点合并成一个集合。将新建点设为根。
不难发现，在进行n-1轮之后我们得到了一棵恰有n个叶子的二叉树，同时每个非叶子节点恰好有两个儿子。这棵树就叫 Kruskal 重构树。
.webp)
这张图的 Kruskal 重构树如下：
void Ex_Kruskal()
{
int cnt = n;
sort(e + 1, e + m + 1, cmp);
for(int i = 1; i < 2*n; ++i) f[i] = i;
for(int i = 1; i <= m; ++i){
int u = get(e[i].x), v = get(e[i].y);
if(u != v){
++cnt;
f[u] = f[v] = cnt;
val[cnt] = e[i].z;
add(cnt,u), add(cnt,v);
if(cnt == 2 * n - 1) break;
}
}
}
欧拉回路
定义
-
欧拉回路：通过图中每条边恰好一次的回路
-
欧拉通路：通过图中每条边恰好一次的通路
-
欧拉图：具有欧拉回路的图
-
半欧拉图：具有欧拉通路但不具有欧拉回路的图
性质
欧拉图中所有顶点的度数都是偶数。
欧拉图，则它为若干个环的并，且每条边被包含在奇数个环内。
证明：反证法： 假设有一条边属于偶数个环的并，那么必然会产生 奇度数点对，所以不能构成欧拉图。
差分约束
定义
差分约束系统，是求解关于一组变量的特殊不等式组之方法。
如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如$$x_j-x_i \leq c_k$$ (i, j∈[1,n], k∈[1,m]), 则称其为差分约束系统。
亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
差分约束系统中的每个约束条件$ x_i-x_j\leq c_k\(都可以变形成\)x_i\leq c_k + x_j$ ,这与单源最短路中的三角形不等式非常$ dist[i]\leq dist[j]+z $相似。
设 \(dist[0]=0\)并向每一个点连一条权重为 \(0\) 边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则，\(x_i=dist[i]\)为该差分约束系统的一组解。
2-SAT
定义
2-SAT，简单的说就是给出\(n\)个二元组，每个二元组有两个元素，已知若干个 \(\langle a,b \rangle\)，表示 \(a\)与 \(b\) 矛盾（其中 \(a\) 与 \(b\) 属于不同的集合）。共多个集合，一般每个集合n个元素，判断能否一共选 \(n\)个两两不矛盾的元素。显然可能有多种选择方案，一般题中只需要求出一种即可。
例
6个二元组：（A1， B1），（D0， B0）， （C1， B0）， （C0， C0）， （A0， D0）， （B0， C1）.
比如（A1， B1）表示如果A（true）那么B（false）， 于是就将A1连边指向B0。
连完所有边后，在这一个有向图中会有很多个强连通分量，而选择一个元素后就必须选完当前强连通分量的所有元素，所以当A0与A1处于同一强连通分量时，方案为0。
二分图
定义
二分图就是将所有节点分成两个集合，且两个集合内部没有边的图。
性质
- 如果两个集合中的点分别染成蓝色和红色，可以发现二分图中的每一条边都一定是连接一个蓝色点和一个红色点。
- 二分图不存在长度为奇数的环。
匹配
匹配
给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
极大匹配
指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。
最大匹配
所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。
- 匈牙利算法\(O(nm)\)
- dinic最大流\(O(\sqrt{n}m)\)
完全匹配(完美匹配)
一个匹配中，图中的每个顶点都和图中某条边相关联。(最大权匹配会碰到这个概念）
覆盖与独立集
最小边覆盖
选择尽量少的边，使得任意一个点相连的边中至少有 一条边被选。
最小点覆盖
选择尽量少的点，使得任意一条边的两端至少有一个 点被选。
最大点独立集
选择尽量多的点，使得任意一条边的两端至多有一 个点被选。
最大边独立集
就是二分图最大匹配
网络流
概念
一个网络 \(G = (V, E)\) 是一张有向图。其中每条有向边$ (x, y) ∈ E$ 都有一 个给定的权值 \(c(x, y)\)，称为边的容量。
图中还有两个指定的特殊节点 \(S ∈ V, T ∈ V\)，分别称为源点和汇点。
定义网络的流函数 f，它满足以下三个条件：
1.容量限制 \(f(x, y) ≤ c(x, y)\)
2.斜对称 \(f(x, y) = −f(y, x)\)
3.流量守恒。
最大流
对于一个给定的网络，其中使得整个网络的流量 \(∑ ^S_{V∈E} f(S, v)\) 最大的 流函数被称为网络的最大流。
Dinic
在任意时刻，网络中所有节点以及剩余容量大于 0 的子图被称为残量 网络。
Dinic 算法不断重复以下步骤，直到在残量网络中 S 不能到达 T。
1.在残量网络中 bfs 求出节点的层次，构造分层图。
2.在分层图中 dfs 寻找增广路，在回溯时实时更新剩余容量。
Dinic 算法的时间复杂度上界为 \(O(n^2m)\)，同样难以到达这个上界，一 般可以处理 1e4 ∼ 1e5 规模的网络。
当前弧优化
因为在Dinic算法中，一条边增广一次后就不会再次增广了，所以下次增广时不需要再考虑这条边。我们记录一下就行了。
费用流
把Dinic的bfs改成spfa就行了。
无源汇上下界可行流
有源汇上下界可行流
有源汇上下界最大流
虚树
给出一棵树.
每次询问选择一些点,求一些东西.这些东西的特点是,许多未选择的点可以通过某种方式剔除而不影响最终结果.
我们可以用log级别的时间求出点对间的lca....
那么,对于每个询问我们根据原树的信息重新建树,这棵树中要尽量少地包含未选择节点. 这棵树就叫做虚树.
接下来所说的"树"均指虚树,原来那棵树叫做"原树".
原树：
因为任意两个关键点的 LCA 也是需要保存重要信息的，所以我们需要保存它们的 LCA，因此虚树中不一定只有关键点。
二次排序 + LCA 连边
因为多个节点的$ LCA$ 可能是同一个，所以我们不能多次将它加入虚树。
非常直观的一个方法是：
- 将关键点按 DFS 排序；
- 遍历一遍，任意两个相邻的关键点求一下$ LCA$，并且判重；
- 然后根据原树中的祖先后代关系建树。
具体实现上，在 关键点序列 上，枚举 相邻的两个数，两两求得 \(lca\) 并且加入序列中。
因为 DFS 序的性质，此时的序列已经包含了 虚树中的所有点，但是可能有重复。
所以我们把序列按照 \(dfn\) 序 从小到大排序并去重。
最后，在序列上，枚举 相邻 的两个 点编号 ，求得它们的\(lca\) 并且连接 ，虚树就构造完成了。
for(int i = 1; i <= m; i++) scanf("%lld", &h[i]);
sort(h + 1, h + 1 + m, cmp);
for(int i = 1; i < m; i++){
k[++len] = h[i];
k[++len] = lca(h[i], h[i + 1]);
}
k[++len] = h[m];
sort(k + 1, k + 1 + len, cmp);
len = unique(k + 1, k + 1 + len) - k - 1;
for(int i = 1, lc; i < len; i++){
vis[k[i]] = vis[k[i + 1]] = 1;
lc = lca(k[i], k[i + 1]);
add_new(lc, k[i + 1], query(lc, k[i + 1]));
}