欧拉路径和欧拉回路

这是之前关于欧拉路的两篇博客。

关于欧拉路的逆序压栈问题：here。

22年写的一个小总结：here。

关于欧拉路，主要疑点在于两个：一是压栈输出的原理；二是打上标记后时间复杂度退化的问题。

• 压栈输出的原理

走到点u时，有两种情况：

1. u此时是终点，那么没有没走过的边与之相连。
2. u此时不是终点，那么它一定还要继续走，也就是还有没走过的边与之相连。

注意：u此时不是终点，不代表它一定不是终点，因为一个点可能重复经过，就好比下面那个图，1号点一开始不是终点，但是最后可能是终点。

qishi

• 打上标记后时间复杂度为何会退化

考虑这样这个图（无向图，有向图的情况，图中的无向边{u, v}改成两条有向边(u,v), (v,u)即可。）：

n=2，只有两个点，共有m条边，现在来看下打标记的做法会遍历多少次边。

记u：cnt，为第cnt次经过u号点。

1:1，此时遍历到h[u]就会递归到2。
2:1，此时遍历到h[u]就会递归到1。
1:1，此时会遍历e[1]，发现边有标记，然后到e[2]，递归到2。
2:2，此时会遍历e[1]，发现边有标记，然后到e[2]，递归到1。
……

观察一下，1：1后，经过了1条边，2：1后，经过了2条边，1:2后经过了3条边，2:2后经过了4条边，1:3经过了5条边……

不难发现，2：x后经过了2x条边，那么也就是说，对于二号点，直到走完了m条边递归才会结束，也就是递归了m/2次。
1号点的递归次数也大致是m/2次。（之所以是大致，是因为根据不同实现方式，可能会多一两个常数）。

对于1号点：1:1，遍历1个出边；1:2遍历2个出边；……1：m/2，遍历m/2个出边，一共遍历了m^2级别的边。

二号点也是如此，所以会超时。

所以此时，我们考虑实时更新h[u]，让后面重复递归的点不再枚举到走过的边，将边真正意义上删除。

然而，此时还没考虑递归结束后回溯的情况。

1:1，回溯之后还会遍历2、3、……m的出边。
1:2，回溯之后还会遍历3、……的出边。

总共也是m^2级别的打过标记的边数。

也就是说，后递归的点总过的边，应当不让之前递归的点再走，可是我们明明已经删去了这条边啊，为什么这样呢？

其实这样的：

我们递归删边的时候，将h[u]连到了后续节点，但是不论怎么连，当前点枚举时候使用的局部变量i都不会被更新。

所以，其实我们的i应当改为h[u]，这样才能保证后续删去的边不会在回溯时被遍历到。