欧拉路与欧拉回路

原理

见《进阶指南》第409页。

边连通的无向图

存在欧拉路的充要条件：度为奇数的顶点有0个或2个。

存在欧拉回路的充要条件：度为奇数的顶点有0个。

边连通的有向图

存在欧拉路的充要条件：要么所有顶点的出度等于入度，要么除了起点的出度=入度+ 1，终点的入度=出度+ 1外，其他顶点的出度等于入度。

存在欧拉回路的充要条件：所有顶点的出度等于入度。

模板题

LibreOJ-10105-欧拉回路

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int N = 100010, M = 200010;
struct edge {
    int to, next;
};
edge e[2 * M];
int idx, head[N], in_deg[N], out_deg[N];
int t, n, m;
bool mark[2 * M];
vector<int> res;

void add_edge (int u, int v) {
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
void dfs (int cur) {
    int& i = head[cur];
    while (i != -1) {
        if (mark[i] == true) {
            i = e[i].next;
            continue;
        }

        mark[i] = true;
        if (t == 1) mark[i ^ 1] = true;

        int eid;
        if (t == 1) {
            eid = i / 2 + 1;
            if (i & 1) eid = -eid;
        } else {
            eid = i + 1;
        }

        int to = e[i].to;
        i = e[i].next;
        dfs(to);
        res.push_back(eid);
    }
}

int main () {
    memset(head, -1, sizeof(head));
    scanf("%d%d%d", &t, &n, &m);
    for (int i = 1, u, v; i <= m; ++ i) {
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        if (t == 1) add_edge(v, u);
        ++ in_deg[v], ++ out_deg[u];
    }

    for (int i = 1; i <= n; ++ i) {
        if (t == 1 && (in_deg[i] + out_deg[i]) % 2 == 1
            || t == 2 && in_deg[i] != out_deg[i]
        ) {
            printf("NO");
            return 0;
        }
    }
    for (int i = 1; i <= n; ++ i) {
        if (head[i] != -1) {
            dfs(i);
            break;
        }
    }
    if (res.size() < m) {
        printf("NO");
        return 0;
    }
    printf("YES\n");
    for (auto i = res.rbegin(); i != res.rend(); ++ i)
        printf("%d ", *i);
    return 0;
}