欧拉路

构造题中的欧拉回路 | tyqtyq 的博客

2018的国家集训队论文《欧拉图相关的生成与计数问题探究》

[Tricks] 记各类欧拉回路问题 - 樱雪喵 - 博客园

欧拉路径是满足恰经过所有边一次的通路

  • 欧拉回路是起点和终点相同的一条欧拉路径.

判别法则：

  • 有向图存在欧拉回路: G中所有度数非0的点是强连通的，且所有点入度均等于出度.
  • 有向图存在欧拉通路:
    • 将边看成无向边后，G中所有度数非0的点是连通的。
    • 最多只有一个点入度比出度大 1，作为欧拉通路的起点
    • 最多只有一个点出度比入度大 1，作为欧拉通路的终点
    • 其他所有点入度均等于出度
  • 无向图存在欧拉回路: G中所有度数非0的点是连通的且所有点度数均为偶数.
  • 无向图存在欧拉通路: G中所有度数非0的点是连通。并且G中恰好存在0或2个奇度点。 其他所有点度数均为偶数。那两个奇度点中, 一个作为欧拉通路之起点, 另一个作为终点.

算法流程：感性理解：先找一条起点到终点的通路，然后不断回溯找环。

先用充要条件也就是度数和连通性去判断是不是存在欧拉路 ，存在的话用dfs构造欧拉路。

有向图最小字典序欧拉路https://www.luogu.com.cn/problem/P7771

  • 当前弧优化保证时间复杂度O(n+m)O(n+m)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> din(n + 1), dout(n + 1);
    vector<int> path;
    vector<vector<int>> e(n + 1);
    vector<int> cur(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        din[v]++;
        dout[u]++;
    }
    for (int i = 1; i <= n; i++) sort(alls(e[i]));
    function<void(int)> dfs = [&](int u) {
        int sz = e[u].size();
        while (cur[u] < sz) {
            int v = e[u][cur[u]];
            cur[u]++;
            dfs(v);
            path.push_back(v);
        }
    };
    auto euler_dir = [&]() {
        int x = 0, y = 0, z = 0;
        for (int i = 1; i <= n; i++) {
            if (din[i] + 1 == dout[i]) {
                x = i;
                y++;
            }
            if (din[i] != dout[i])
                z++;
        }
        bool flag = ((y == 1 && z == 2) || (z == 0));
        if (flag == 0)
            return false;
        if (x == 0) {
            for (int i = 1; i <= n; i++)
                if (din[i]) {
                    x = i;
                    break;
                }
        }
        dfs(x);
        path.push_back(x);
        if ((int)path.size() != m + 1)
            return false;
        reverse(alls(path));
        return true;
    };
    if (euler_dir()) {
        for (auto x : path) cout << x << " ";
    } else {
        cout << "No" << endl;
    }
}

无向图最小字典序欧拉路:寻找起点的时候保证起点是最小的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
struct node {
    int v, idx;
    bool operator<(const node &other) {
        return v < other.v;
    }
};
void solve() {
    int n = 500, m;
    cin >> m;
    vector<int> deg(n + 1);
    vector<int> cur(n + 1);
    vector<bool> vis(2 * m + 10);
    int cnt = 1;
    vector<vector<node>> e(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        deg[u]++;
        deg[v]++;
        cnt++;
        e[u].push_back({v, cnt});
        cnt++;
        e[v].push_back({u, cnt});
    }
    for (int i = 1; i <= n; i++) sort(alls(e[i]));
    vector<int> path;
    function<void(int)> dfs = [&](int u) {
        int sz = e[u].size();
        while (cur[u] < sz) {
            auto [v, idx] = e[u][cur[u]];
            if (vis[idx] == 0) {
                vis[idx] = vis[idx ^ 1] = true;
                cur[u]++;
                dfs(v);
                path.push_back(v);
            } else {
                cur[u]++;
            }
        }
    };
    auto euler = [&]() {
        int x = 0, y = 0;  // 保证字典序最小
        for (int i = n; i >= 1; i--) {
            if (deg[i] & 1) {
                x = i;
                y++;
            }
        }
        if (y > 0 && y != 2)
            return false;
        if (x == 0) {
            for (int i = 1; i <= n; i++) {
                if (deg[i]) {
                    x = i;
                    break;
                }
            }
        }
        dfs(x);
        path.push_back(x);
        if ((int)path.size() != m + 1)
            return false;
        reverse(alls(path));
        return true;
    };

    if (euler()) {
        for (auto x : path) cout << x << endl;
    } else {
        cout << "NO" << endl;
    }
}

无向图欧拉回路：正向边输出边的编号，反向边输出相反数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
struct node {
    int v, idx, res, op;
    //idx是每个方向边编号,res是无向边共用的编号，op表示正边反边
    bool operator<(const node &other) {
        return v < other.v;
    }
};
// 只找欧拉回路
void solve1() {  // 无向图
    int n, m;
    cin >> n >> m;
    vector<int> deg(n + 1);
    vector<int> cur(n + 1);
    vector<bool> vis(2 * m + 10);
    int cnt = 1;
    vector<vector<node>> e(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        deg[u]++;
        deg[v]++;
        cnt++;
        e[u].push_back({v, cnt, i, 1});
        cnt++;
        e[v].push_back({u, cnt, i, 2});
    }
    vector<int> path;
    function<void(int)> dfs = [&](int u) {
        int sz = e[u].size();
        while (cur[u] < sz) {
            auto [v, idx, res, op] = e[u][cur[u]];
            if (vis[idx] == 0) {
                vis[idx] = vis[idx ^ 1] = true;
                cur[u]++;
                dfs(v);
                if (op == 1)
                    path.push_back(res);
                else
                    path.push_back(-res);
            } else {
                cur[u]++;
            }
        }
    };
    auto euler = [&]() {
        int x = 0, y = 0;  // 保证字典序最小
        for (int i = n; i >= 1; i--) {
            if (deg[i] & 1) {
                x = i;
                y++;
            }
        }
        if (y > 0)
            return false;
        if (x == 0) {
            for (int i = 1; i <= n; i++) {
                if (deg[i]) {
                    x = i;
                    break;
                }
            }
        }
        dfs(x);
        // path.push_back(x);
        if ((int)path.size() != m)
            return false;
        reverse(alls(path));
        return true;
    };

    if (euler()) {
        cout << "YES" << endl;
        for (auto x : path) cout << x << " ";
    } else {
        cout << "NO" << endl;
    }
}

有向图欧拉回路：输出路径的边的编号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
struct node2 {
    int v, id;
};
void solve2() {  // 有向
    int n, m;
    cin >> n >> m;
    vector<int> din(n + 1), dout(n + 1);
    vector<int> path;
    vector<vector<node2>> e(n + 1);
    vector<int> cur(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back({v, i});
        din[v]++;
        dout[u]++;
    }
    function<void(int)> dfs = [&](int u) {
        int sz = e[u].size();
        while (cur[u] < sz) {
            auto [v, res] = e[u][cur[u]];
            cur[u]++;
            dfs(v);
            path.push_back(res);
        }
    };
    auto euler_dir = [&]() {
        int x = 0, y = 0, z = 0;
        for (int i = 1; i <= n; i++) {
            if (din[i] + 1 == dout[i]) {
                x = i;
                y++;
            }
            if (din[i] != dout[i])
                z++;
        }
        bool flag = (z == 0);
        if (flag == 0)
            return false;
        if (x == 0) {
            for (int i = 1; i <= n; i++)
                if (din[i]) {
                    x = i;
                    break;
                }
        }
        dfs(x);
        // path.push_back(x);
        if ((int)path.size() != m)
            return false;
        reverse(alls(path));
        return true;
    };
    if (euler_dir()) {
        cout << "YES" << endl;
        for (auto x : path) cout << x << " ";
    } else {
        cout << "NO" << endl;
    }
}