图论
欧拉图
欧拉路径：经过图中每条边恰好一次。
存在欧拉回路的图称为欧拉图，只有欧拉路径的图称为半欧拉图。
下面三个条件是等价的：
$G$ 是欧拉图。
$G$ 中每个点的度数都是偶数。
$G$ 可被分解为若干条不共边回路的并
连通性相关
1. $\text{DFS}$ 生成树
有向图经过 $\text{DFS}$ 序标号后，所有的边可以分为以下几类：
树边：指向 $\text{DFS}$ 生成树的子节点。
返祖边：指向祖先节点的边。
横叉边：指向先前访问过的非祖先节点。
前向边：指向（更深层的）子树节点，非树边。
而在无向图中，一定不存在横叉边，因为访问其中一个节点时另一个一定会被纳为子节点。
2. 强联通分量 / $\text{SCC}$
定义：极大强联通子图，内部节点互相可达。
Tarjan 算法
我们需要维护的有：
每个节点的 $\text{DFN}$ 序 $dfn[u]$。
从根到当前节点的路径的栈。
$low[u]$，代表 $u$ 的子树中能回溯到的最早的栈中节点。
假定当某个节点出栈后，其所在所有联通分量已经处理完成，那么我们就不必考虑符合此情况的横叉边和前向边。如果是树边，那么用 $low[v]$ 去更新 $low[u]$；如果是返祖边，则用 $dfn[v]$ 去更新 $low[u]$。
当出现 $dfn[u]=low[u]$ 的情况时，意味着我们找到了一个 $\text{SCC}$。不断弹出进行标记即可。
- 可以将每个 $\text{SCC}$ 缩成一个点，从而得到 $\text{DAG}$。
3. 割点和桥
割点 / 割顶
定义：删去此点后图中极大联通分量数增加。
仍然是利用 Tarjan 算法，类似地记录 $dfn[u]$ 和 $low[u]$。由于这里是无向边，就记录为不经过其 $\text{DFS}$ 的父节点（可达但不过），能到达的标号最小的点。
如果一个点是割点，那么：
如果该点是根节点，只需要满足与其直接相连的点的数量 $\geq 2$。
否则，需要存在其某个子节点 $v$ 满足 $low[v]\geq dfn[u]$。
割边 / 桥（无重边）
定义：删去此边后图中极大联通分量数增加。
割边的考虑更为简单，只需要让 $low[v]>dfn[u]$，且不需要考虑根节点。
割边 / 桥（有重边）
记录刚刚走过的边的编号 $fa$，将“不用父节点更新”改为“不用已经走过的边更新”。
另一种思路，是标记判断是否已经有一条边联通父节点，已有再更新。
4. 双联通分量
（默认在无向连通图中）
点双联通：无论删去哪一个除了 $u$ 和 $v$ 之外的点，都不能使 $u$ 和 $v$ 不联通。
边双联通：无论删去哪一条边，都不能使 $u$ 和 $v$ 不联通。
- 边双具有传递性，而点双不具有。
点（边）双联通分量：极大点（边）双联通子图。
边双联通分量
- Tarjan - 1
求出所有的桥，再 $\text{DFS}$。
- Tarjan - 2
等价于求 $\text{DFS}$ 生成树上的强联通分量。
- 差分算法
考虑一个树边什么情况下会变成桥。显然非树边不会是桥，因为还有一条树边组成的路径与其等价。那么没有被覆盖的树边就是桥。在深度较大的点 $+1$，较小的 $-1$，线性处理子树价值和。如果 $cnt[u]=cnt[v]$，代表从 $u$ 到 $v$ 的树边没有被其他非树边覆盖，从而是桥。然后再用一遍 $\text{DFS}$ 求答案。
点双联通分量
- Tarjan
参考性质：
两个点双最多有一个公共点，且这个点一定是割点。
对于一个点双，其 $dfn$ 最小的点一定是割点或者树根。
如果是割点，则是点双的根。
如果是树根：
有至少两个（$\text{DFS}$ 生成树中的）子树，则是一个割点（无向图不存在横叉边）。
只有一个子树，则是点双的根。
没有子树，则视作单独的点双。