欧拉回路

欧拉回路的定义是：对于一个图，如果从一个点出发，遍历所有的边后回到出发的那一个点，那么这个图就含有欧拉回路。

欧拉回路其实和小学时学习的一笔画问题有关系。

一笔画问题中，我们可以得出有两种图可以一笔画：每个点只有偶数个边连着的，或者只有两个点有奇数个边连着。

第一种情况，就是欧拉回路。

所以，欧拉环路的性质是：

• 对于无向图，每个点的读都是偶数。
• 对于有向图，每个点的初读和入度相同。

输出

这里的遍历输出需要加一点技巧。

第一个点：

正常的 DFS 是在函数的开头就输出：

void dfs(int i) {
    if (vis[i]) continue;
    vis[i] = 1;
    cout << XXX;
    for () {
        dfs(j)
    }
}

而输出欧拉回路的时候，输出要放在函数的最后面，也就是回溯的时候再输出。关键点

第二个点：

欧拉回路的 DFS 的 vis 数组应当按边去记录，而不是点。关键点

欧拉路径

之前我们讲过一笔画问题的规律，其中第二种规律就是欧拉路径。

欧拉路径的定义是：一个图，如果可以从一个点，走完所有的路，那么这个图就含有欧拉路径。

当欧拉路径形成一个环的时候，这个图就有欧拉回路。

欧拉路径的性质（严格）：

• 对于无向图：有 $2$ 个奇数度的顶点
• 对于有向图：有一个点的出度比入度大 $1$，一个顶点的入度比出度大 $1$，其他顶点的出度和入度一样。