USACO图论题解析：欧拉回路算法实现与应用

1. 项目背景与题目解析

P6066 [USACO05JAN] Watchcow S是美国计算机奥林匹克竞赛(USACO)的一道经典图论题目。这道题出现在2005年1月的月赛中，属于银组难度，考察选手对图遍历算法的理解和应用能力。

题目描述：农场主John的奶牛们总是喜欢在夜间偷偷溜出牛棚。为了防止这种情况，John决定在牧场的某些交叉路口安装监控摄像头。牧场可以看作是一个无向图，其中交叉路口是顶点，道路是边。John希望安排监控路线，使得每条道路都能被双向监控（即每条边被经过两次，方向相反），并且最终能回到起点。

这道题本质上要求我们找到一个有向图的欧拉回路。欧拉回路是指经过图中每条边恰好一次且最终回到起点的路径。在无向图中，欧拉回路存在的充要条件是图连通且所有顶点的度数都是偶数。对于有向图，则需要每个顶点的入度等于出度。

2. 解题思路与算法选择

2.1 问题转化

首先我们需要将原始的无向图问题转化为有向图问题。因为题目要求每条道路被双向监控（即每条无向边需要被两个方向各走一次），我们可以将每条无向边转化为两条方向相反的有向边。

例如，如果原图有无向边(u, v)，则我们创建两条有向边u→v和v→u。这样处理后，新图中的每个顶点的入度和出度必然相等（因为每条无向边都为每个顶点贡献了1个入度和1个出度），因此这个有向图必定存在欧拉回路。

2.2 算法选择

寻找欧拉回路的经典算法是Hierholzer算法，其时间复杂度为O(E)，非常适合本题。算法基本步骤如下：

1. 从任意顶点开始深度优先搜索
2. 沿着未访问的边前进，直到无法继续（即当前顶点的所有出边都已被访问）
3. 将当前顶点加入路径，并回溯到上一个顶点
4. 如果还有未访问的边，从路径上的某个顶点重新开始搜索
5. 最终将路径逆序输出即为欧拉回路

对于本题，我们需要特别注意边的处理顺序，确保每条边都被恰好访问一次。

3. C++实现详解

3.1 数据结构设计

我们使用邻接表来表示图，同时需要记录每条边是否已被访问。由于每条无向边对应两条有向边，我们需要一个有效的方式来标记边的访问状态。

cpp复制#include <iostream>
#include <vector>
#include <stack>
using namespa