原题连接

tag: 图论，欧拉回路，*2500

题意

给出一个连通无向图， 个点 条边，边分成必选边和非必选边，可以存在重边和自环，要求选出一条路径包含所有的必选边，并且选出的路径上所有边（必选边和非必选边）只经过一次，并且能够回到起点。

题解

由于路径上每条边只经过一次，并且要形成一个环，不难想到最后如果答案存在一定构成一条欧拉回路。回想欧拉回路的性质，每个点的度数都是偶数，且连通，因此题目的意思是：是否可以删掉原图中一些非必选边，使得剩下的图包含一个欧拉回路，也就是所有点的度数都是偶数。

有了这个想法后，发现代码并没有很容易实现。如果一开始用所有的边建图，然后考虑删掉一些边使得所有点的度数均为偶数，这样的做法很难找到删掉哪些边能够满足条件。

考虑反过来，如果我们从必选边开始，逐渐加入非必选边，那么最后的图一定是一个欧拉回路。因此我们可以从必选边开始，逐渐加入非必选边，如果最后的图是一个欧拉回路，那么就符合题意。

一个比较容易实现的方法是考虑非必选边所构成的子图，用 dfs 进行遍历，在 dfs 遍历的过程中，如果发现一个点的度数为奇数，则删掉和它父亲相连的一条边，使得这个点的度数变成偶数，最后如果根节点的度数是奇数，说明不能满足所有点的度数都是偶数的条件。

最后在所有选出的边中跑一边求欧拉回路即可。

时间复杂度

代码

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
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> d(n + 1);
    vector<vector<int>> G(n + 1);
    vector<int> u(m + 1), v(m + 1), w(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> w[i];
        if (w[i]) d[u[i]]++, d[v[i]]++;
        G[u[i]].push_back(i), G[v[i]].push_back(i);
    }

    vector<bool> vis(n + 1);
    auto dfs = [&](auto dfs, int x) -> void {
        vis[x] = true;
        for (int i : G[x]) {
            int y = u[i] ^ v[i] ^ x;
            if (vis[y] || w[i] == 1) continue;
            dfs(dfs, y);
            if (d[y] & 1) {
                d[x]--, d[y]--;
                w[i] = 1;  // 选
            }
        }
    };

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) dfs(dfs, i);
        if (d[i] & 1) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";

    vector<int> ans;

    // 这种找欧拉回路T了
    // auto dfs2 = [&](auto dfs2, int x) -> void {
    //     for (int i : G[x]) {
    //         if (w[i] == 0) continue;
    //         int y = u[i] ^ v[i] ^ x;
    //         w[i] = 0;
    //         dfs2(dfs2, y);
    //     }
    //     ans.push_back(x);
    // };

    auto dfs2 = [&](auto dfs2, int x) -> void {
        while (G[x].size()) {
            int i = G[x].back();
            G[x].pop_back();
            if (w[i] == 0) continue;
            int y = u[i] ^ v[i] ^ x;
            w[i] = 0;
            dfs2(dfs2, y);
        }
        ans.push_back(x);
    };

    dfs2(dfs2, 1);

    cout << ans.size() - 1 << endl;
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " \n"[i == ans.size() - 1];
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。