Graph Theory

若图 \(G\) 中存在一个子图 \(G'\)，\(G'\) 中任意两点均可互相到达，则称 \(G'\) 为 \(G\) 的一个强连通分量。若 \(G'\) 不存在一个严格子图为强连通分量，则 \(G'\) 为 \(G\) 的极大强连通分量。

参考代码：

• 欧拉路径：如果图中的一个路径包括每个边恰好一次，则该路径称为欧拉路径。
• 欧拉回路：首尾相接的欧拉路径被称为欧拉回路。

由于每一条边都要经过恰好一次，因此对于除了起点和终点之外的任意一个节点，只要进来，一定要出去，故有如下结论：

有时候我们需要维护一些具有传递性的关系，如相等，连通等。

初始条件往往是给定几组关系，要把所有的关系求出来。

可以把 Floyd 算法做一些调整：

但是 Dijkstra 算法要求所有边权均非负，于是就有了重赋权的技巧。

接下来证明这样做为什么是对的：

首先有定义 ：

最常用且大部分情况下效率最高的最小生成树算法。

将边按长度从小到大排序，每次贪心选择最短的一条边，若这条边连接的两个点还为连通，则将两个点所在的连通块用这条边连接，连通块用并查集维护。

时间复杂度 \(\Theta(m\log m)\)。

在稠密图上复杂度最优的最小生成树算法。

差分约束是用来解形如 \(x_{1}-x_{2}\leqslant k\) 的若干个方程的算法。

另外，如果有负环则无解。

时间复杂度 \(\Theta(\rm SPFA)\)。

需要注意的是，最短路求的是以起始点为基准的最大解，而最长路求的是以起始点为基准的最小解。

\(\rm Prufer\) 序列可以将一颗结点数为 \(n\) 的有标号无根树用一个长度为 \(n-2\)，值域为 \([1,n]\) 的数列唯一表示，即有标号无根树和 \(\rm Prufer\) 序列呈双射关系。

具体来说，有标号无根树的构建方式如下：

\(2-\rm Sat\) 问题是求解某个 \(\rm bool\) 方程组，方程组中的每个方程被描述为：\(x_{i}\) 为真\(/\)假 或 \(x_{j}\) 为真\(/\)假。

对树上每个点建立一个 \(\rm bool\) 变量，取值为 \(1\) 表示这个点选。

并查集可以用来维护一类具有传递性的关系，维护形如将 \(x\) 与 \(y\) 所在集合合并和询问 \(x\) 和 \(y\) 是否在同一个集合的操作。

对于普通并查集来说，有路径压缩和按秩合并等优化，路径压缩一般实现如下 ：

按秩合并则取点数小的连向点数大的即可。