Luogu P6066 [USACO05JAN] Watchcow S 题解 欧拉回路

题目链接：Luogu P6066 [USACO05JAN] Watchcow S 欧拉回路
题目描述：

给定一张无向图，输出任意一条从一号结点出发的欧拉回路（欧拉回路指每条无向边来回经过且只经过一次），给定的图保证这样的欧拉回路存在。

题解：

只需要从一号结点开始使用Hierholzer算法进行遍历即可。对于一个存在欧拉回路或者欧拉通路的图Hierholzer算法的思想是一直在图中找环，每找到一个环就将这个环从图中删除。具体地：

1. 遍历到某个结点时，找到一个以当前结点为起点的环，如果不存在这样的环，则退出；
2. 从图中删除当前找到的环经过的边，然后依次从当前的环上的每个点遍历，即回到1。
3. 将遍历的当前结点加入到栈中。

上述的过程保存的结点依次从栈中弹出，则是一条以传入结点开始的欧拉回路或者欧拉通路。
在实际实现中我们知道DFS算法可以找环，所谓的删除边的操作，我们则可以每遍历一条边即将边给删除，这样只需要一次遍历即可找到欧拉回路或者欧拉通路（因此时间复杂度为O(n+m)），对于边的删除操作，如果使用邻接矩阵存边，我们没访问一次便执行connect[u][v]--操作，对于邻接表我们可以通过给每一条边增加一个deleted的标志，遍历之后将deleted置为true或者使用一个cnt数组，cnt[u]表示u结点应该从第几条边开始遍历，每遍历一条边便使cnt[u]++即可达到删除边的操作，使用链式前向星也可以通过增加deleted标志来实现删除边的效果。具体可以参见代码实现。
特别地，对于需要按照字典序进行遍历的情况而言，我们需要使用邻接表存边，这样才能够进行排序。除此之外，对于有些题目会要求无向边只经过一次，我们在删除边的时候需要将其反向边也给删除掉，而如果使用邻接表进行存边的话，我们需要保存反向边的编号，同时对于自环需要额外注意反向边的编号差异，而如果使用链式前向星则可以通过i^1的方式很容易的获取到反向边，因此对于这种题目推荐使用邻接表保存排序后（如果需要的话），对邻接表进行遍历再通过链式前向星保存图（由于链式前向星后加入的边会先遍历，因此排序时往往需要逆序）。

代码：LuoguP6066