作者：SovietPower✨
链接：https://ac.nowcoder.com/discuss/186584
来源：牛客网
度数序列
对于无向图，
为每个点的度数。有
（每条边被计算两次）。有偶数个度数为奇数的点。
Havel–Hakimi算法
给定一个由有限多个非负整数组成的度数序列，是否存在一个简单图使得其度数序列恰为这个序列。
令
为有限多个非负整数组成的非递增序列。
可简单图化当且仅当有穷序列
只含有非负整数且是可简单图化的。
序列
可简单图化是指存在一个无向图（无重边无自环），使得其度数序列恰为
。
（这个其实就是很显然的东西。。主要是一个定义）
Erdős–Gallai定理
令
为有限多个非负整数组成的非递增序列。
可简单图化当且仅当这些数字的和为偶数，且
，对于任意
都成立。
也不难理解。对前
个点分配度数，除了两两能连
条边外，剩下的度数由后面点的度数补。
因为
非递增，从小到大枚举
，维护
后缀与
取
的和（
都是单调的，维护从哪开始
的结果是
）。就可以
判断了。
例题：Good Bye 2018 E，NEERC2013 K.Kids in a Friendly Class。
欧拉路与欧拉回路
给定一张无向/有向图，求一条经过所有边恰好一次的回路。有解当且仅当所有点 度数为偶数(无向)/入度等于出度(有向)。任选一点开始dfs，每条边只经过一次。回溯时将回溯的边加入队列，最后队列的逆序就是答案。时间复杂度
。
欧拉路径也可以用一样的方法求出（找度数为奇数的点进行DFS）。
欧拉回路：
- 有向图：所有点的出度入度都相等；从任意一点都可实现。
- 无向图：所有点度数都为偶数。
：
- 有向图：有两个点可以入度出度不相等（差不大于一），即起点终点；起点入度小于出度，终点入度大于出度 。
- 无向图：仅有两个点度数为奇数。
注：必须为连通图（用并查集判断）。两笔画问题
：
有解当且仅当入度为奇数的点不超过四个。将其中两个点加一条边后求欧拉路径，然后在这条边处断开成两条欧拉路即可。时间复杂度
。
题目：UOJ#117(模板)、题集。
Prufer序列
这里很全，可以看这儿。
Defination：
Prufer序列是一种无根树的编码表示。
对于一棵
个点的无根树，对应唯一一串长度为
的
序列。
无根树转
序列
定义无根树中度数为
的节点是叶子节点，每次找到编号最小的叶节点删除，在序列中添加与之相邻的点。如此重复直到剩下最后两个节点。
上图对应无根树的
序列为
。
序列转有根树
给定点集
，
序列
。
每次取出
序列中的第一个元素
，在
中找在当前
序列中没有出现的第一个元素
，在
和
间连一条边；将
从
序列中删除，
从
中删除。最后
中还剩下
个元素，在这
个元素间连一条边。
生成树计数
Cayley定理：完全图的生成树个数为
。如果每个点的度数为
，那么生成树个数为
。每个连通块大小为
，那么添加一些边将这些连通块连通的生成树个数为
。
题目：题集。
Matrix-Tree定理
无向图生成树计数：令
（基尔霍夫矩阵=度数矩阵-边矩阵），然后去除
的任意一行一列得到
，
的行列式即生成树个数。
有向图生成树计数：与无向图不同的是，
矩阵为入度/出度矩阵分别对应外向树/内向树。且删掉第
行第
列表示以
为根节点的生成树个数。
题目：题集。
最小生成树 Borůvka算法
一开始每个连通分量是一个点本身。
每轮枚举所有属于不同连通分量的边，每个连通分量选择和其他连通分量相连的最小的边，然后合并。
每轮连通块个数至少减半，所以最多进行
轮。时间复杂度
。
具体实现直接用并查集即可。代码可以看这里。
题目一般用来做边权与点权相关，还是个完全图，求MST的题？
1. 有
个点的完全图，每个点的权值为
，两个点之间的边权为
。求这张图的最小生成树。
2.CF888G。有一张
个点的完全图，每个点的权值为
，两个点之间的边权为
。求该图的最小生成树。
。
最小瓶颈生成树
使得生成树树上最大边权值最小。
方法1：最小生成树一定是最小瓶颈生成树。
方法2：二分答案，看点是否连通。
方法3：类比找第k大值的方法(`nth_element`)，首先随机一个边权$w$。然后将不超过这个边权的边加入，遍历这张图。
如果图连通，那么瓶颈不超过$w$，于是只需考虑边权不超过$w$的边；否则将这些连通点缩起来，考虑边权大于$w$的边。
每次将问题的规模缩小至一半。期望时间复杂度$T(m)=T(frac m2)+O(m)=O(m)$。
单源最短路(SSSP)
（贪心）或者
（动态规划）。
时间复杂度
或者
。
一些变种
边权是
：双端队列，如果是
在头部插入，否则在尾部插入。
最长路径不超过
, 正权图：使用
的桶+链表维护这些点（代替堆），时间复杂度
。
关于判负环
复杂度
。代码实现可以记录最短路树上的深度来判环，而不是入队次数，这样会有优化。
if
差分约束
大体过程：（具体可以看这里）
考虑最短路中的松弛操作：
，也就是强制使得
满足
。
所以对于
的限制，可以连一条边
。这样求
的最大值，就是求
的最短路。
如果限制是
，同理连边
。
的最小值就是求
的最长路。
如果两种限制都有，就把
变成
。
解的存在性：
比如求
的最大值：若图中存在负环，则
的最短路无穷小，则不存在最大值（无解）。若
和
就不在同一连通块，则
的最短路无穷大，最大值无穷大（或者存在无数多解）。
否则有解。
PS：
可以根据入队次数判负环，也可以据此判正环。虽然效率都不高就是了。
不能求最长路（本质是贪心）。
如何判断解唯一：
对原图求一遍最短路。将原图取反，边权取反，求一遍最长路。
一个标号对应的是能取到的最小值，一个是最大值。
如果相同则解唯一。（没什么用）
题目：题集。
多源最短路(APSP)
算法（可用于负权图）：
算法
原理：首先给图中每个点一个权值
，把每条边的边权
改成
。
对于$
的一条路径
，权值为
所以这么做不会改变最短路。（具体也可以看这里）
实现：第一次SPFA预处理$1$到每个点的距离
，记
。然后把边权
改为
。
其中$
为给每个点设定的权值，
。
由不等式可以得到
，也就是改完之后所有边权非负。
之后可以每个点用
跑。就是
啦。
这样也可以实现
跑费用流。
半径 直径 (正权图)
（后面可能就直接抄dls课件了QAQ）
的偏心距
直径
半径
中心
（要求定义在点上）
绝对中心（可以定义在边上）
绝对中心
相关：求最小直径生成树（差不多）。
实现：固定一条
，考虑上面的点
的偏心距。
假设第三个点是
，
。
那么对应的折线为
。
那么偏心距为
条折线的最大值形成的折线。
按左端点排序维护一下。时间复杂度
最小直径生成树
即绝对中心的最短路树。
如何证明？
注意一棵树
的直径为半径的两倍(对绝对中心来说)。如果最小直径生成树$T’$不包含绝对中心，那么取
的绝对中心
，显然矛盾。
拓扑排序
每次去掉图中入度为$0$的点。
时间复杂度
。
如果最后不为空集，那么这个图不为DAG。（否则每个点入度不为0，即每个点可以选择一个前趋，沿着前趋走根据抽屉原理一定能找到相同点，也就是一个环。）
按照反图DFS，出栈序列就是一个合法的拓扑序列。
scc缩点顺序也是一个合法拓扑序。
求字典序最小的拓扑序
每个点有不同的标号，要使得拓扑序最小。
将拓扑排序的队列改成优先队列即可。
最小拓扑序的一个变种
使得最后的拓扑序中1的位置尽量靠前，如果相同比较2的位置，依次类推。
首先考虑如何求1最早出现的位置，可以将原图反向，然后每次弹除了1之外的元素，直到队列只剩下1为止。
这是反图中1的最晚的出现的位置，也就是原图中最早的。
根据是否在队列里，这个图被分成两部分，在对应的图中用同样的方法处理2，依次类推。
容易发现每次找尽量大的元素出队，能完成上述的过程。
所以等价于反图最大字典序。
题目：题集。
二分图匹配
Hall's marriage theorem（霍尔定理）
对于一个二分图
，记
为
的一个子集，
为所有
中所有点的相邻点的并集。
一个图有完备匹配当且仅当
的所有子集
都有
。
对一般图的推广：
：每个正则二分图都有完备匹配。
Kőnig's theorem
最小点覆盖=最大匹配 (与最大流最小割定理等价)
最大独立集=点数-最大匹配 (独立集为点覆盖的补集)
最小边覆盖=最大独立集 (独立集中每个点需要一条边去覆盖)
DAG最小路径覆盖
覆盖所有的边：每条边下界设为1, 然后求最小流。
覆盖所有的点：建立二分图，对于
的边，看做二分图中的
，然后答案为点数-最大匹配。
定理: 最大反链=最小链覆盖；最短的最长链=最小反链划分数-1（？存疑。见BZOJ4160）。（当然这个不应该只放在二分图部分的）
题目：题集。
连通分量
强连通分量
。
将一个图的所有强联通分量缩起来会得到一个DAG。
双联通分量
点连通度: 最小的点集使得删去之后图不连通
边连通度: 最小的边集使得删去之后图不连通
如果一个图的点连通度大于1，那么是点双连通的，边连通同理。
双联通分量为图中的极大双联通子图。
割点和桥
考虑DFS树，每条非树边对应着一个点到祖先的路径。对于一条非树边只要把对应的边打上标记即可。
比如对于$(u,v)$这条非树边，只要在$u$点打上$+1$的标记，$v$点打上$-1$的标记。
$x$到$fa[x]$的树边的覆盖次数为子树内所有标记的和。
割点同理（注意特判根节点和叶节点）。
（emm没看懂下面要干嘛）
：题集。
2-SAT
一堆变量的二元限制，问是否存在合法的赋值。
：例题，题集。
曼哈顿距离与切比雪夫距离
将原坐标系每个点的坐标
变为
，则原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离。
反过来，将原坐标系每个点的坐标
变为
，则原坐标系中的切比雪夫距离等于新坐标系中的曼哈顿距离。
例题：BZOJ3170 松鼠聚会。
与作者交流：https://ac.nowcoder.com/discuss/186584
更多算法和题解：https://ac.nowcoder.com/acm/contest/discuss