思路与算法

对每个原连通块，只看c=1边产生的奇度顶点数o：有奇边的块至少需要max(1,o/2)人，无奇边块无需人。构造时奇边放一次，偶边放两次以保证原块连通；把所有奇度点各接一条到虚点的边，得到欧拉结构。Hierholzer后在虚点处切开，偶度且有奇边的独立块输出一条闭路。

正确性说明

每条人的路径只能产生0或2个奇端点，因此o个奇点至少o/2条；全偶但有边仍至少一条。复制偶边不改变要求奇偶，接虚点使度数全偶。切虚边后恰得到o/2条原图路径；无奇点块的欧拉闭路是一条。每条原边最终出现奇偶与c一致，叠加已有次数变偶，所以达到下界。

复杂度

并查集与邻接初始化O(n+m)量级，欧拉遍历O(n+m)，空间O(n+m)，输出长度O(n+m)。全文件Σn,Σm≤5e5时构造路径节点总数小于5e6限制。

易错点

偶边可以走两次，不能只在c=1子图中按分量计人数。没有奇边的原分量不输出无用路线。特判核实最小人数、每步有边、总长度以及最终全部边偶数。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<int> p(n), has(n), odd(n);
        iota(p.begin(), p.end(), 0);
        function<int(int)> find = [&](int x) {
            while (p[x] != x) {
                p[x] = p[p[x]];
                x = p[x];
            }
            return x;
        };
        struct E {
            int u, v, c;
        };
        vector<E> es(m);
        for (auto &e : es) {
            cin >> e.u >> e.v >> e.c;
            --e.u;
            --e.v;
            p[find(e.u)] = find(e.v);
            if (e.c)
                odd[e.u] ^= 1, odd[e.v] ^= 1;
        }
        for (auto e : es)
            if (e.c)
                has[find(e.u)] = 1;
        vector<vector<pair<int, int>>> g(n + 1);
        int M = 0;
        auto add = [&](int u, int v) {
            g[u].push_back({v, M});
            g[v].push_back({u, M++});
        };
        for (auto e : es)
            if (has[find(e.u)]) {
                add(e.u, e.v);
                if (!e.c)
                    add(e.u, e.v);
            }
        for (int u = 0; u < n; u++)
            if (odd[u])
                add(n, u);
        vector<int> used(M), pos(n + 1);
        vector<vector<int>> ans;
        auto run = [&](int root) {
            vector<int> st(1, root), tour;
            while (!st.empty()) {
                int u = st.back();
                while (pos[u] < (int)g[u].size() && used[g[u][pos[u]].second])
                    pos[u]++;
                if (pos[u] < (int)g[u].size()) {
                    auto e = g[u][pos[u]++];
                    used[e.second] = 1;
                    st.push_back(e.first);
                } else {
                    tour.push_back(u);
                    st.pop_back();
                }
            }
            reverse(tour.begin(), tour.end());
            vector<int> part;
            for (int x : tour) {
                if (x == n) {
                    if (part.size() > 1)
                        ans.push_back(part);
                    part.clear();
                } else
                    part.push_back(x);
            }
            if (part.size() > 1)
                ans.push_back(part);
        };
        if (!g[n].empty())
            run(n);
        for (int u = 0; u < n; u++) {
            while (pos[u] < (int)g[u].size() && used[g[u][pos[u]].second])
                pos[u]++;
            if (pos[u] < (int)g[u].size())
                run(u);
        }
        cout << ans.size() << '\n';
        for (auto &a : ans) {
            cout << a.size();
            for (int u : a)
                cout << ' ' << u + 1;
            cout << '\n';
        }
    }
}