欧拉回路：通过图中每条边恰好一次的回路

欧拉通路：通过图中每条边恰好一次的通路

欧拉图：具有欧拉回路的图

半欧拉图：具有欧拉通路但不具有欧拉回路的图

无向图求欧拉通路/回路

// n点m边，可重边自边
int n, m;
cin >> n >> m;
vector<int> deg(n), del(m); // deg[i]点i的度，del[i]编号i的边是否删除
vector<vector<pair<int,int>>> g(n); // g[i] i的出边 连接点和编号
for (int i=0; i<m; i++) {
    int x, y;
    cin >> x >> y;
    deg[x]++;
    deg[y]++;
    g[x].emplace_back(y, i);
    g[y].emplace_back(x, i);
}

vector<int> stk; // 欧拉通路/回路所经过的点，若为有向图则是逆序
function<void(int)> euler = [&](int u) {
    while(g[u].size()) {
        auto [v, e] = g[u].back();
        g[u].pop_back();
        if (del[e]) continue;
        del[e] = 1;
        euler(v);
    }
    stk.push_back(u);
};
// deg 只存在两个奇数，其余为偶数，则存在欧拉通路
// deg 只存在偶数，则存在欧拉回路
for (int i=0; i<n; i++) {
    if (deg[i]%2) {
        euler(i); // 欧拉通路从奇数度开始
        break;
    }
}
if (stk.empty()) euler(0); // 不存在奇数度，欧拉回路可从任意一点开始
for (int i:stk) {
    cout << i << " ";
}
cout << "\\n";

有向图欧拉通路/回路

// n点m边，可重边自边
int n, m;
cin >> n >> m;
vector<int> deg(n), del(m); // deg[i] 点i的出度-入度，del[i]编号i的边是否删除
vector<vector<pair<int,int>>> g(n); // g[i] i的出边 连接点和编号
for (int i=0; i<m; i++) {
    int x, y;
    cin >> x >> y;
    deg[x]++;
    deg[y]--;
    g[x].emplace_back(y, i);
}

vector<int> stk; // 欧拉通路/回路所经过的点，若为有向图则是逆序
function<void(int)> euler = [&](int u) {
    while(g[u].size()) {
        auto [v, e] = g[u].back();
        g[u].pop_back();
        if (del[e]) continue;
        del[e] = 1;
        euler(v);
    }
    stk.push_back(u);
};

// deg 只存在一个1和-1，其余为0，则存在欧拉通路
// deg 只存在0，则存在欧拉回路
for (int i=0; i<n; i++) {
    if (deg[i] == 1) {
        euler(i); // 欧拉通路从出度-入度=1开始
        break;
    }
}
if (stk.empty()) euler(0); // 不存在奇数度，欧拉回路可从任意一点开始
reverse(stk.begin(), stk.end());
for (int i:stk) {
    cout << i << " ";
}
cout << "\\n";