[Note] 欧拉回路与路径

[L4] 欧拉回路与路径

1. 生态位

• 识别:

  1. 一笔画: 经过图中每条边恰好一次，且不重复。

  2. 回路 vs 路径: 回到起点（回路）；不回到起点（路径）。

• 地位：图论基础的连通性分支。它是点连通性（Hamilton）的对偶问题，但欧拉回路有好多项式时间的解法，而 Hamilton 是 NP-Hard。

• 用途: 解决“边全覆盖”类的连通性问题，以及将一维序列重组为图的路径。

2. 逻辑支点

2.1 判定定理

这是欧拉回路存在的充要条件，也是解题的第一步 check。

• 无向图:

  • 回路: 所有点的度数都是偶数。

  • 路径: 恰好有 0 个 或 2 个 奇度数点。

    • 若有 2 个，则这两个点必定是起点和终点。

• 有向图:

  • 回路: 所有点的 入度等于出度 ($in[u] == out[u]$)。

  • 路径: 恰好有一个点 $out = in + 1$ (起点)，一个点 $in = out + 1$ (终点)，其余点 $in == out$。

2.2 核心原理：Hierholzer 算法

为什么不能直接 DFS？

• 直接 DFS 可能会过早地回到起点，导致还有一部分边（子环）没得跑。

Hierholzer 的直觉:

• 一直跑: 只要有路就走，直到无路可走（陷入死胡同或回到起点）。

• 回溯录像: 当一个点“无路可走”时，把它加入路径栈。

• 物理意义: 这相当于我们在回溯时，把沿途发现的“小圈”慢慢合并到主路径上。最后倒序输出栈，就是正确的欧拉路径。

3. 实战部署

▶

Hierholzer (DFS)

const int maxn = 100010;
const int maxm = 200010;

vector< int > adj[maxn];
int cur[maxn]; // 当前弧优化：记录搜到了第几条边
stack< int > stk; // 记录欧拉路径（倒序）
int n, m;

// 针对有向图的 DFS
void dfs( int u )
{
    // 引用 &i，确保随着递归深入，cur[u] 也会增加
    // 这种写法类似网络流的当前弧优化，保证每条边只被遍历一次 O(M)
    for( int &i = cur[u]; i < adj[u].size( ); )
    {
        int v = adj[u][i];
        
        // 逻辑删边：先移指针，再递归
        // 无向图需要在此处通过 flag 标记反向边防止走回头路
        i ++; 
        
        dfs( v );
    }
    
    // 核心：回溯时入栈
    stk.push( u );
}

void get_euler( int start )
{
    dfs( start );
    
    // 检查是否所有边都走过
    // if( stk.size() != m + 1 ) -> No Solution
    
    while( !stk.empty( ) )
    {
        cout << stk.top( ) << " ";
        stk.pop( );
    }
    cout << '\n';
}

4. 知识关联

• 母题: P7771 模板 欧拉路径 —— 有向图欧拉路径的标准模板，需处理字典序最小。

• 关联笔记：存图与遍历 | [[网络流专题]]