题意简述

给定一个无向图，边分为两类：必须走的（$c=1$）和可选走的（$c=0$）。要求找一条闭合回路（起点终点相同），不重复经过任何一条边，且恰好经过每条必须边一次。保证必须边构成的图连通。判断是否存在这样的回路，并输出方案。

算法思路

问题等价于：求一个包含所有必须边的欧拉回路。欧拉回路存在的充要条件是图连通且所有顶点度数为偶数。必须边已经连通所有点，我们只需借助可选边调节顶点的度数奇偶性。

1. 统计度数：只考虑必须边时，计算每个顶点的度数（即与其相连的必须边条数）。目标是通过选择性保留部分可选边，使得最终所有顶点度数为偶数。
2. 利用可选边调节奇偶性：
   • 构建仅由可选边组成的图。
   • 在该图上进行 DFS，任选未访问的点开始。
   • 对于每条可选边 $(u,v)$，若 $v$ 尚未访问，则递归访问 $v$。处理完子树后，若 $v$ 当前的度数为奇数，则保留这条可选边（即最终图中包含它），并翻转 $u$ 和 $v$ 的度数（相当于在最终度数上各加 $1$）。
3. 合法性检查：遍历结束后，若存在任意顶点的度数仍为奇数，则无解，输出 NO。
4. 构造欧拉回路：在保留的边集（所有必须边 + 筛选出的可选边）上运行 Hierholzer 算法（深度优先遍历，每次取一条未删除的边，删除后递归），即可得到一条合法回路。由于必须边连通且可选边不会破坏连通性，整个图是连通的且所有点度数为偶数，欧拉回路必定存在。
5. 输出：输出保留的边数（即原总边数减去删去的可选边数）以及回路节点序列。

时间复杂度 $O(n + m)$，空间复杂度 $O(n + m)$。能轻松处理 $5\times 10^5$ 的数据规模。

参考代码

#include<bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    cin >> tests;
    while (tests--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> black(n);
        vector<int> edg(m);
        vector<vector<int>> g(n);
        for (int i = 0; i < m; ++i) {
            int x, y, c;
            cin >> x >> y >> c;
            --x, --y;
            edg[i] = x ^ y;
            g[x].push_back(i);
            g[y].push_back(i);
            if (c == 0) {
                black[x].push_back(i);
                black[y].push_back(i);
            }
        }
        vector<int> deg(n);
        for (int i = 0; i < n; ++i) deg[i] = g[i].size() & 1;
        vector<bool> del(m, false), used(n, false);
        auto dfs = [&](auto dfs, int u) -> void {
            used[u] = true;
            for (auto id : black[u]) {
                int to = edg[id] ^ u;
                if (used[to]) continue;
                dfs(dfs, to);
                if (deg[to]) {
                    del[id] = true;
                    deg[to] ^= 1;
                    deg[u] ^= 1;
                }
            }
        };
        bool ok = true;
        for (int i = 0; i < n; ++i) {
            if (used[i]) continue;
            dfs(dfs, i);
            ok &= !deg[i];
        }
        if (!ok) {
            cout << "NO\n";
            continue;
        }
        auto euler = [&](auto euler, int u) -> void {
            while (!g[u].empty()) {
                int id = g[u].back();
                g[u].pop_back();
                int to = edg[id] ^ u;
                if (del[id]) continue;
                del[id] = true;
                euler(euler, to);
            }
            cout << u + 1 << ' ';
        };
        cout << "YES\n";
        cout << m - accumulate(del.begin(), del.end(), 0) << '\n';
        euler(euler, 0);
        cout << '\n';
    }
}