浅谈欧拉图（欧拉路径）

定义

通过图中所有边恰好一次的通路称为欧拉通路。

通过图中所有边恰好一次的回路称为欧拉回路。

具有欧拉回路的无向图或有向图称为欧拉图。

具有欧拉通路但不具有欧拉回路的无向图或有向图称为半欧拉图。

非形式化地讲，欧拉图就是从任意一个点开始都可以一笔画完整个图，半欧拉图必须从某个点开始才能一笔画完整个图。

性质

欧拉图中所有顶点的度数都是偶数。

判别法

对于无向图G，G是欧拉图当且仅当  是连通的且没有奇度顶点。

对于无向图G，G是半欧拉图当且仅当G是连通的且G中恰有0个或2个奇度顶点。

对于有向图G，G是欧拉图当且仅当G的所有顶点属于同一个强连通分量且每个顶点的入度和出度相同。

对于有向图G，G是半欧拉图当且仅当

• 如果将G中的所有有向边退化为无向边时，那么G的所有顶点属于同一个连通分量。
• 最多只有一个顶点的出度与入度差为1。
• 最多只有一个顶点的入度与出度差为1。
• 所有其他顶点的入度和出度相同。

上述有向图G且G为半欧拉图可以简单说为满足以下两个性质其中之一即可

1.有向图G中所有顶点的入度与出度相等

2.有向图G中有且只有一个顶点的入度为其出度+1（该点为终点），并且有且只有一个顶点的出度为其入度+1（该点为起点），其他点的入度与出度相等

求解欧拉路径可以使用Fleury算法（避桥法）时间复杂度为O()，可用性不大

一般求解欧拉路径使用Hierholzer算法（逐步插入回路法），不求字典序最小的欧拉路径时的时间复杂度为O(n+m)，求字典序最小的欧拉路径时，需要对每个点所能到达的点进行从小到大排序，因此时间复杂度为O(n+mlogm)

【模板】欧拉路径 - 洛谷

求解字典序最小的欧拉路径

AC代码：

#include 
using namespace std;
using LL = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vectorint>> G(n + 1);
    vector<int> in(n + 1), out(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        out[u]++;
        in[v]++;
    }
    int st = -1, end = -1, zz;
    bool ok = true;
    for (int i = 1; i <= n; i++) {
        if (in[i] == out[i]) {
            zz = in[i];
            continue;
        }
        else {
            if (in[i] == out[i] + 1 and end == -1) {
                end = i;
            }
            else if (out[i] == in[i] + 1 and st == -1) {
                st = i;
            }
            else {
                ok = false;
                break;
            }
        }
    }
    if (!ok) {
        cout << "No\n";
        exit(0);
    }
    for (int i = 1; i <= n; i++) {
        sort(G[i].begin(), G[i].end());
    }
    if (st == -1) {
        st = 1;
    }
    stack<int> sta;
    vector<int> cur(n + 1);
    function<void(int)> dfs = [&](int x) {
        int len = G[x].size();
        for (int i = cur[x]; i < len; i = cur[x]) {
            cur[x] = i + 1;
            dfs(G[x][i]);
        }
        sta.push(x);
    };
    dfs(st);
    while (!sta.empty()) {
        cout << sta.top() << ' ';
        sta.pop();
    }
    return 0;
}