欧拉图
-
欧拉回路：通过图中每条边恰好一次的回路(走完必须回到刚开始的点)
-
欧拉通路：通过图中每条边恰好一次的通路(不必须)
-
欧拉图：具有欧拉回路的图
-
半欧拉图：具有欧拉通路但不具有欧拉回路的图
欧拉图的判定方法 ：
判定无向图是欧拉图：非零度顶点是连通的，顶点的度数都是偶数
判定无向图是半欧拉图：非零度顶点是连通的，恰有 2 个奇度顶点
判定有向图是欧拉图：非零度顶点是强连通的，每个顶点的入度和出度相等
判定有向图是半欧拉图：非零度顶点是弱连通的，至多一个顶点的出度与入度之差为 1，
至多一个顶点的入度与出度之差为 1 吗，其他顶点的入度和出度相等
计算欧拉回路/通路的算法 ：
Fleury 算法
不常用，暂不介绍。
Hierholzer 算法
也称逐步插入回路法。
以问题为例：
即输出字典序最小的欧拉路径
Q：如何判定是否存在欧拉回路？欧拉通路呢？
(挖坑....)
算法类似模板：
auto dfs = [&](auto&& self, int x) -> void {
for (int& i = cur[x]; i < m; i++) {
if (g[x][i]) {
g[x][i] = g[i][x] = 0;
self(self, i);
}
}
a.push_back(primes[x]);
};
dfs(dfs, 0);
目前的应用场景：
!1981(div2)