欧拉回路和欧拉路径（ccf路径）

欧拉路径和欧拉回路

1.欧拉路径：把一个图上所有边都访问一次的路径（每条边只能走一次）。
2.欧拉回路：从起点出发最后回到起点的欧拉路径。
3.如果一个图存在欧拉回路，那么也存在欧拉路径。
B站一个老外讲的原理，中文字幕，临近6级，可以锻炼一下听力。

大前提：所有度非0的点，都必须属于同一个连通分量

下面这张图是不符合的：

一.无向图

1. 满足欧拉回路的条件：每个节点都有偶数的度。
2. 满足欧拉路径的条件：除了每个节点都有偶数的度，还可以让两个节点有奇数的度，这两个点就是欧拉路径的起点和终点。

二.有向图
3. 满足欧拉回路的条件：每个节点都有相同的入度和出度。
4. 满足欧拉路径的条件：如果存在欧拉路径，最多只有 一个顶点的入度 - 出度 = 1， 且最多只有1个顶点的出度 - 入读 = 1。并且其他所有节点的入度=出度。

下面是一道关于欧拉路径的ccf题目（路径）

参考这位大牛的博客
(https://blog.****.net/Touchig/article/details/84804871)
以及Hierholzer’s Algorithm算法
https://www.geeksforgeeks.org/hierholzers-algorithm-directed-graph/
我就着上面那位大牛的代码记录一下我的理解：

1. vector<set> 利用set直接实现字典序最小（set自带的从小到大排列特性）。
2. 判断是否存在欧拉路径的特判。
3. 对上面提及到的大前提的特判
4. 还有就是最巧妙之处，对图上边是否走过的记录方法（Hierholzer’s Algorithm），直接删掉走过的边（因为有set存图保证了字典序最小）。