寻找有向图中的欧拉回路（Hierholzer算法）

题目描述
给定一个有向图，判断其是否存在欧拉回路。如果存在，则找出一条经过图中每条边恰好一次的回路。欧拉回路要求从某顶点出发，沿着有向边行走，最终回到起点，且每条边被访问一次。

解题过程

1. 欧拉回路的存在性判定

• 条件1：图是强连通的（任意两点互相可达）。
• 条件2：每个顶点的入度等于出度。
  原因：进入顶点的边数必须等于离开的边数，才能保证路径连续且回到起点。

2. Hierholzer算法的核心思想

• 从任意顶点开始，进行深度优先遍历，直到无法继续（形成一个临时回路）。
• 回溯时，若当前顶点还有未访问的边，则从此顶点开始新的深度遍历，形成子回路，并将其插入主回路中。
• 最终合并所有子回路，形成欧拉回路。

3. 算法步骤详解
步骤1：检查存在性条件。

• 使用 Kosaraju 或 Tarjan 算法验证强连通性。
• 遍历所有顶点，检查入度与出度是否相等。

步骤2：初始化数据结构。

• 使用邻接表存储图，并记录每个顶点未访问的边（或使用边的访问标记）。
• 准备一个栈（或链表）circuit，用于存储最终回路。

步骤3：递归深度优先遍历（DFS 变体）。

Hierholzer(v):
  当 v 有未访问的出边时：
    选择一条边 (v, u)，标记为已访问
    递归调用 Hierholzer(u)
  将 v 加入 circuit

• 注意：递归结束后将顶点加入 circuit，确保回路顺序正确。

步骤4：反转输出。

• 由于顶点是回溯时加入的，最终需将 circuit 反转，得到从起点开始的欧拉回路。

4. 示例演示
考虑有向图：
顶点：0, 1, 2
边：0→1, 1→2, 2→0

• 每个顶点入度=出度=1，且强连通，存在欧拉回路。
• 从0开始：
  • 访问0→1，递归到1
  • 访问1→2，递归到2
  • 访问2→0，递归到0（无未访问边）
  • 回溯依次将0、2、1、0加入circuit
• 反转后得到回路：0→1→2→0。

5. 复杂度与注意事项

• 时间复杂度：O(E)，每个边处理一次。
• 需注意图可能包含多条边或自环，算法需兼容。
• 若图不满足存在性条件，直接返回无解。

通过以上步骤，可系统性地求解有向图的欧拉回路问题。