欧拉回路
欧拉回路
2023.09 updated
一、基本概念欧拉路径：从图中一个结点出发走出一条道路，每条边恰好经过一次的路径。
欧拉回路：从图中任意一个顶点出发走出一条道路，每条边恰好经过一次，并最终回到起点。这样的路径称为“欧拉回路”。（类似于一笔画问题）
欧拉图：具有欧拉回路的图。
半欧拉图：具有欧拉路径但不具有欧拉回路的图
二、算法实现对于求欧拉回路，我们可以分为两种情况解决：
无向图的欧拉回路(图a、b)：对于无向图，只要是一个连通图并且每个点的度是偶数，那么这个图就能构成欧拉回路。
有向图的欧拉回路(图c、d)：对于有向图，只要是一个连通图并且每个点的入度等于出度，那么这个图就能构成欧拉回路。
对于求欧拉路径，我们也可以分为两种情况解决：
无向图的欧拉路径：对于无向图，只有是一个连通图，并且两个点的度为奇数，剩余为偶数是，那么这个图就能有欧拉路径。
有向图的欧拉路径：对于有向图，只要是一个连通图，并且一个点的入度等于出度加一，一个点的入度等于出度减一，其余点入度等于出度时，这个图就有欧拉路径。
一个欧拉图一定有欧拉路径。
2.1 $\quad$ 无向图的 ...
有向图的连通性
有向图的连通性
一、基本概念强连通：在有向图 $G$ 中，如果两点 $u$ , $v$ 是互相可达的，则称 $u$ 和 $v$ 是强连通的。如果 $G$ 中的任意两个点都是互相可达的，那么 $G$ 就是强连通图。
强连通分量：如果一个有向图 $G$ 不是强连通图，那么可以把它分成多个子图，其中每个子图的内部是强连通的，而且这些子图已经扩展到最大，不能与子图外的任一点强连通，像这样的一个“极大强连通”子图是$G$的一个强连通分量( $\text{Strongly Connected Component}$，$\text{SCC}$ ).
$Tarjan$算法能在一次DFS中吧所有点都按 $\text{SCC}$ 分开。这并不是不可思议的，它利用了 $\text{SCC}$ 的特点。
定理：一个 $\text{SCC}$，从其中任何一个点出发。都至少有一条路径能绕回到自己。
二、算法实现在讲解之前，先了解$low$和$num$操作。
下面是一个例子，下图有三个 $\text{SCC}$，也就是$\{a,b,d,c\}$、$\{e\}$、$\{f\}$.
图1.a是原图。图1.b是对它做$ ...
线段树
线段树
线段树，OI中重要的数据结构，用于维护区间信息，也可以辅助维护。线段树的性能比树状数组强（但是码量大），普遍复杂度在 $O(\log n)$ 左右。
一、基本概念线段树是一种二叉树，也就是对于一个线段，我们会用一个二叉树来表示。比如说一个长度为4的线段，我们可以表示成这样：
这是什么意思呢？ 如果你要表示线段的和，那么最上面的根节点的权值表示的是这个线段 $1\sim 4$ 的和。根的两个儿子分别表示这个线段中 $1\sim 2$ 的和，与 $3\sim 4$ 的和。以此类推。
然后我们还可以的到一个性质：节点i的权值=她的左儿子权值+她的右儿子权值。因为 $1\sim 4$ 的和就是等于 $1\sim 2$ 的和加上 $3\sim 4$ 的和。
根据这个思路，我们就可以建树了，我们设一个结构体 tree，tree[i].l 和 tree[i].r 分别表示这个点代表的线段的左右下标， tree[i].sum 表示这个节点表示的线段和。
我们知道，一颗二叉树，她的左儿子和右儿子编号分别是 $p\times2$ 和 $p\times2+1$。
再根据刚才的性质，得到式子：tree ...
