消圈算法讲解笔记

总结

因为中间节点度数都为偶数，有一条入边对应着也会有一条出边离开，所以图中会出现环。
考虑环的链接方式，无非也就是两种，环连环， 和环连边。易证这两种方式都存在一条路径覆盖所有边。
考虑一种构造欧拉路径的通用方式，考虑 dfs ，问题在 dfs 的回溯上，考虑回溯后继续向下 dfs 的部分的结构。由于中间节点的度数都为 偶数 ，显然图是由一主干 + 若干环结构组成，所以回溯后的情况就相当于上述的两种结构，回路的话同理，只是主干同样也是一个环，即在一个大环周围镶嵌若干小环。
这里如果同学对环有疑问的话，可以解释：
（考虑同学对从中间一个点出发一定会绕一个环然后回到出发点吗？即出去的路径和回来的路径不在一个环里）这是一定的，由于入度都等于出度，所以如果存在一条进入某个点的边，那么一定就存在一条出边，又由于图是连通的，边的数量是有限制值，那么在有限步之内一定会回到起点。
算法原理即证明如上，可能看着比较繁琐，但代码实现起来其实并不难

算法具体实现过程：
整体框架（伪代码）
for(u~nxt[i])
{
for(以u为起点的边)
dfs(v ) ;
seq <- u ;
}
具体实现如上。（easy
观察实现过程，加入当前的起点 u 时 u 的所有“子节点”均已加入序列。所以该序列是欧拉路径的倒序。
/*
针对某些同学对正序正确性的疑问：

“一个点的出边可能有多条，有些出边可能要回溯的时候才能访问到，如果遍历到的时候直接正序记录，那么终点/终边可能就会出现在回溯后才能访问到的点/边前面”

再形象一点：
“理解首个的概念会更好一些，因为终点无路可走(欧拉回路因为所有边被访问过)，
所以按照后序逻辑加点不论什么访问顺序到终点都是首个，
但是先序逻辑则一旦终点先被遍历，而有的边未遍历则从终点回溯时终点已经在该边/点之前,
所以不论正看反看都是无序的”
*/
优化：
1、回忆普通 dfs 的写法，即用点判重。在所有节点均被标记后，算法结束，复杂度 （n + m）。但针对欧拉路径来说，由于路径定义的特殊性，必须采用用边判重。这时不妨考虑每个点有 m 条自环，对于路径中的每个起点都需遍历每条连出的边，复杂度（n * m）。复杂度不优秀。
这里使用一种 “用完即删” 的方式来保证每条边只能被遍历一次，复杂度（n + m）
2、对于无向图的双向边同时删除，由于我们使用连续的下标来储存双边（0 ， 1）（2 ， 3）（4 ， 5）……这里在删除编号为 k 的边时，同时删除 k ^ 1 即他的反向边。

例题AcWing1123

随着白天越来越短夜晚越来越长，我们不得不考虑铲雪问题了。

整个城市所有的道路都是双向车道,道路的两个方向均需要铲雪。因为城市预算的削减，整个城市只有 1 辆铲雪车。

铲雪车只能把它开过的地方（车道）的雪铲干净，无论哪儿有雪，铲雪车都得从停放的地方出发，游历整个城市的街道。

现在的问题是：最少要花多少时间去铲掉所有道路上的雪呢？

输入格式

输入数据的第 $1$ 行表示铲雪车的停放坐标 $(x,y)$，$x,y$ 为整数，单位为米。

下面最多有4000行，每行给出了一条街道的起点坐标和终点坐标，坐标均为整数，所有街道都是笔直的，且都是双向车道。

铲雪车可以在任意交叉口、或任何街道的末尾任意转向，包括转 $U$ 型弯。

铲雪车铲雪时前进速度为 $20$ 千米/时，不铲雪时前进速度为 $50$ 千米/时。

保证：铲雪车从起点一定可以到达任何街道。

输出格式

输出铲掉所有街道上的雪并且返回出发点的最短时间，精确到分钟，四舍五入到整数。

输出格式为”hours:minutes”，minutes不足两位数时需要补前导零。
具体格式参照样例。

数据范围

$-10^6 \le x,y \le 10^6$
所有位置坐标绝对值不超过 $10^6$。

输入样例：

0 0
0 0 10000 10000
5000 -10000 5000 10000
5000 10000 10000 10000

输出样例：

3:55

样例解释

输出结果表示共需3小时55分钟。