欧拉路径 & 欧拉回路

定义

• 欧拉路径：经过连通图中所有边恰好一次的迹称为 欧拉路径。
  
• 欧拉回路：经过连通图中所有边恰好一次的回路称为 欧拉回路。即首尾相连的欧拉路径。
  
• 欧拉图：具有欧拉回路的图称为 欧拉图。
  
• 半欧拉图：具有欧拉路径但不具有欧拉回路的图称为 半欧拉图。
  

不经过重复边的途径称为 迹。

判定

• 有向图欧拉路径：图中恰好存在 \(1\) 个点的出度比入度多 \(1\) （该点即为起点 \(S\)），\(1\) 个点的入度比出度多 \(1\) （该点即为终点 \(T\)），其余点的出度等于入度。
  
• 有向图欧拉回路：图中所有点的入度等于出度（起点 \(S\) 和终点 \(T\) 可以为任意点）。
  
• 无向图欧拉路径：图中恰好存在 \(2\) 个点的度数是奇数，其余点的度数为偶数，这两个度数为奇数的点即为欧拉路径的起点 \(S\) 和终点 \(T\) 。
  
• 无向图欧拉回路：图中所有点的度数都是偶数（起点 \(S\) 和终点 \(T\) 可以为任意点）。
  

注意：存在欧拉路径的充要条件是无向图连通，有向图弱连通。

对于有向图的两点 \(u, v\) ，若将有向边改为无向边后 \(u, v\) 连通，则称 \(u, v\) 弱连通。

构造

采用 Hierholzer 算法求解欧拉路径或欧拉回路。
具体地，遍历当前点 \(u\) 的所有出边 \(u \rightarrow v\)。若该边未走过，则向点 \(v\) DFS。遍历完所有出边后，将 \(u\) 加入回路。最终得到一条反向的欧拉回路，将其翻转即可。
代码实现上，有向弱连通图删边比标记边的 \(O(m^2)\) （其中 \(m\) 是边数）时间复杂度更优。可以用数组维护邻接矩阵，也可以用 vector 或链式前向星维护时间复杂度更优的邻接表。
以欧拉路径的模版题为例，要求有向弱连通图中字典序最小的欧拉路径。由于点数 \(n\) 和边数 \(m\) 均是 \(10^5\) 级别的数据，领接矩阵的 \(O(n^2)\) 的时间复杂度不可接受。考虑采用类似链表的方式记录数组 \(nxt\)，其中 \(nxt_u\) 表示 \(u\) 的邻接表中下一个访问的边的编号。初始时 \(nxt_u = 0\) 即可。考虑通过排序贪心地将点的编号越小的点排在最前面，最终求得的一定是字典序最小的欧拉路径。以下代码的时间复杂度为 \(O(n + m \log m)\)。
点击查看代码[code]#include using namespace std;const int N = 1e5 + 8;int n, m, in[N], out[N], nxt[N];vector e[N];stack stk;void dfs(int u) {    for (int i = nxt; i < e.size(); i = nxt) {        nxt = i + 1;        dfs(e);    }    stk.push(u);}int main() {    cin >> n >> m;    for (int i = 1, u, v; i > u >> v;        e.push_back(v);        out++; in[v]++;    }    for (int i = 1; i > v;        e.push_back(v);        out++; in[v]++;    }    for (int i = 1; i