【图论】欧拉回路和欧拉通路

定义

下面讨论的图 (G) 均不存在孤立顶点（度数为0的顶点）。

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

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

若图 (G) 是欧拉图，则它为若干个边不重复的回路的并。
若图 (G) 是半欧拉图，则它为若干个边不重复的回路和一条简单路径的并。

欧拉图和半欧拉图判定的充要条件
对于无向图 (G) ， (G) 是欧拉图，当且仅当 (G) 是连通的，且没有度数为奇数的顶点。
对于无向图 (G) ， (G) 是半欧拉图，当且仅当 (G) 是连通的，且恰好有0个或2个度数为奇数的顶点。
对于有向图 (G) ， (G) 是欧拉图，当且仅当 (G) 的所有顶点属于同一个强连通分量，且每个顶点的入度和出度相同。
对于有向图 (G) ， (G) 是半欧拉图，当且仅当下列四个条件全部满足：
　　若把有向边换成无向边， (G) 是连通的；
　　且最多一个顶点的入度和出度差为1；
　　且最多一个顶点的出度和入度差为1；
　　除上述的两个顶点外，其他所有顶点的入度和出度相同。

代码

无向图欧拉回路

n       顶点数
m       无向边数
visv    在dfs1中，顶点i是否被遍历过（用于判断存在欧拉回路）
vise    在dfs2中，无向边i是否被遍历过（用于构造欧拉回路）
ans     构造欧拉回路的结果

initialize                  初始化图
addEdge                     向图中加边
existEulerianCircuit        判断存在欧拉回路，复杂度O(n)。
constructEulerianCircuit    构造欧拉回路，复杂度O(n+m)。

struct UndirectGraphEulerianCircuit {

    int n, m;
    vector<vector<pii>> G;

    vector<bool> visv;
    vector<bool> vise;
    vector<int> ans;

    void initialize(int n, int m) {
        this->n = n, this->m = m;
        G.clear();
        G.resize(n + 1);
        visv.clear();
        visv.resize(n + 1);
        vise.clear();
        vise.resize(m + 1);
    }

    void addEdge(int u, int v, int eid) {
        G[u].emplace_back(v, eid);
        G[v].emplace_back(u, eid);
    }

    void dfs1(int u) {
        visv[u] = 1;
        for (const pii &e : G[u]) {
            int v = e.first;
            if (!visv[v])
                dfs1(v);
        }
    }

    bool existEulerianCircuit() {
        for (int i = 1; i <= n; ++i) {
            if (G[i].size() & 1)
                return 0;
        }
        int comp = 0;
        for (int i = 1; i <= n; ++i) {
            if (G[i].size() && !visv[i]) {
                ++comp;
                if (comp >= 2)
                    return 0;
                dfs1(i);
            }
        }
        return 1;
    }

    void dfs2(int u, int peid) {
        while (G[u].size()) {
            pii e = G[u].back();
            G[u].pop_back();
            int v = e.first, eid = e.second;
            if (vise[eid])
                continue;
            vise[eid] = 1;
            dfs2(v, eid);
        }
        if (peid != -1)
            ans.emplace_back(peid);
    }

    void constructEulerianCircuit() {
        ans.clear();
        for (int i = 1; i <= n; ++i) {
            if (G[i].size()) {
                dfs2(i, -1);
                break;
            }
        }
        reverse(ans.begin(), ans.end());
    }

} G;

拓展

构造欧拉通路：先判断欧拉通路存在。若欧拉回路存在，找出欧拉回路输出。若欧拉通路存在，连接一条附加边使得欧拉回路存在，找出欧拉回路，然后把附加边删除。
构造字典序最小的欧拉回路：对每个点的出边排序，并且从字典序最小的起点开始，每一步贪心选择。
构造混合图欧拉回路：转化为网络流问题。

练习

CF1361C - Johnny and Megan's Necklace
CF1038E - Maximum Matching