星空穿越

GitHub跳转原题关系图返回列表

把 c=1 的边当成待消的奇偶约束:每个连通块内生成树边放双份补连通、奇数度点接一个虚点,跑欧拉回路并按虚点切开,即得最少人数。

OJ: roj

题目 ID: 1740

难度:提高+/省选-

标签:图论欧拉回路构造python

创建: 2026-10-07 22:27

更新: 2026-10-07 22:27

形式化题目

给一张 nn 个点、mm 条边的无向简单图 G=(V,E)G=(V,E),每条边带一个标记 ce∈{0,1}c_e \in \{0,1\}: ce=1c_e=1 表示这条通道"已经被经过了奇数次"。要求安排尽量少的行走

P1,P2,…,PK,Pi=(vi,1,vi,2,…,vi,li),P_1, P_2, \dots, P_K, \qquad P_i = (v_{i,1}, v_{i,2}, \dots, v_{i,l_i}),

每个 PiP_i 是 GG 中的一条路径(走法)——相邻两点必须相邻连边,点与边都允许重复经过—— 使得对每条边 ee

∑i=1K[边 e 在 Pi 里出现的次数]  ≡  ce(mod2).\sum_{i=1}^{K} \bigl[\text{边 } e \text{ 在 } P_i \text{ 里出现的次数}\bigr] \;\equiv\; c_e \pmod 2 .

输出第一行是人数 KK,随后 KK 行给出每人的走法;答案不唯一, 判题只看方案的合法性(人数最少 + 每条边的经过次数奇偶正确 + 格式合法)。

记 S={e∈E:ce=1}S = \{e \in E : c_e = 1\} 为"必须被走奇数次"的边集,本文下面一律用 SS 说话。

正解

思路

先把问题翻译成度数的奇偶。 把人看成"给每条边走若干次",只有次数的奇偶有价值, 于是每个 PiP_i 只看它走过奇数次的那些边,得到一个边集 Qi⊆EQ_i \subseteq E。 对任意一个片 PiP_i,把它首尾相接看成一个点序列:序列内部每个点被"进一次出一次", 出现在奇数次的位置只有起点 vi,1v_{i,1} 和终点 vi,liv_{i,l_i}(首尾相同时一个都没有)。因此

∂Qi  =  {{vi,1,vi,li}vi,1≠vi,li∅vi,1=vi,li\partial Q_i \;=\; \begin{cases}\{v_{i,1}, v_{i,l_i}\} & v_{i,1} \ne v_{i,l_i}\\ \varnothing & v_{i,1} = v_{i,l_i}\end{cases}

其中 ∂\partial 是"奇度顶点集",而且它是 F2\mathbb{F}_2 上的线性映射。题目要求的是 ⨁iQi=S\bigoplus_i Q_i = S,两边取 ∂\partial 得

∂S  =  ⨁i∂Qi.\partial S \;=\; \bigoplus_i \partial Q_i .

下界一:按连通块分头算。 每个行走始终待在某一个连通块里,所以 SS 在某个连通块 CC 内的部分 SCS_C 只能由落在 CC 里的行走消掉(不同块之间互不干扰)。设

TC={v∈C:v 在 SC 中度数为奇数},∣TC∣ 必为偶数,T_C = \{v \in C : v \text{ 在 } S_C \text{ 中度数为奇数}\}, \qquad |T_C| \text{ 必为偶数},

则由 ∂SC=⨁∂Qi\partial S_C = \bigoplus \partial Q_i 且每个 ∂Qi\partial Q_i 的大小 ≤2\le 2,得 ∣TC∣≤2kC|T_C| \le 2k_C,即 kC≥∣TC∣/2k_C \ge |T_C|/2;另外当 TC=∅T_C = \varnothing 而 SC≠∅S_C \ne \varnothing 时, CC 里至少得有人(否则 SCS_C 没人消),所以

Kmin⁡  ≥  ∑C{∣TC∣/2∣TC∣>01∣TC∣=0, SC≠∅  =  ∑C: SC≠∅max⁡(1,∣TC∣2).K_{\min} \;\ge\; \sum_{C}\begin{cases} |T_C|/2 & |T_C| > 0\\ 1 & |T_C| = 0,\ S_C \ne \varnothing \end{cases} \;=\;\sum_{C:\,S_C \ne \varnothing} \max\Bigl(1, \tfrac{|T_C|}{2}\Bigr).

关键洞察:一次行走不必是简单路径,可以把好几块 SCS_C 串起来。 QiQ_i 并不需要连通:走法在一条 c=0c=0 的边上"折返一趟"(来回各一次)就等于走它两次, 奇偶上白白消失,却能把两片 SCS_C 接进同一个行走。题面样例就是这么干的: SS 里两块分别是 {1,…,6}\{1,\dots,6\} 和三角形 {7,8,9}\{7,8,9\},参考输出把三角形挂到了 “4→2→7→8→9→7→2→54 \to 2 \to 7 \to 8 \to 9 \to 7 \to 2 \to 5” 这条走法上(22–77 来回各一次)。 所以下界里只有 ∣TC∣/2|T_C|/2 这一项是硬的,"每块至少一个人"只对 TC=∅T_C=\varnothing 的块成立。

上界(构造):把两块东西塞进同一个欧拉回路。 固定一个连通块 CC,做三件事:

  1. 取 CC 的生成树 T\*T^\*,把每条树边放 2 份。它只是让图形连通,取 2 份所以不改变任何点的度数奇偶;
  2. 放入 SCS_C 的全部边,每边 1 份;
  3. 若 TC≠∅T_C \ne \varnothing,再加一个虚点 XX,向 TCT_C 里每个点连一条边。

记这张多重图

MC  =  2 T\*  ∪  SC  ∪  {{X–v:v∈TC}TC≠∅∅TC=∅M_C \;=\; 2\,T^\* \;\cup\; S_C \;\cup\; \begin{cases}\{X\text{–}v : v \in T_C\} & T_C \ne \varnothing\\ \varnothing & T_C = \varnothing\end{cases}

它有两件好性质:

  • 偶度:点 vv 的度数 =2deg⁡T\*(v)⏟偶+deg⁡SC(v)+[v∈TC]= \underbrace{2\deg_{T^\*}(v)}_{\text{偶}} + \deg_{S_C}(v) + [v \in T_C], 后两项同奇偶,加起来是偶数;虚点 XX 的度数是 ∣TC∣|T_C|,也是偶数。
  • 连通:树边双份已经把 CC 的每个点连起来了,XX 又只连 CC 内的点。

于是 MCM_C 有欧拉回路。TC=∅T_C = \varnothing 时整条回路就是一个人的走法(首尾同点, 输出时首点要重复出现在末位);TC≠∅T_C \ne \varnothing 时从 XX 出发,回路每经过一次 XX 就把"进去一次、出来一次"两条虚边用掉,XX 在回路里出现 ∣TC∣/2|T_C|/2 次, 把回路在这些位置切开、丢掉虚点,恰好得到 ∣TC∣/2|T_C|/2 条走法,每条的两端都落在 TCT_C 里。 MCM_C 的边全是 GG 的真边(只有虚边是"刀口",不输出),所以切出来的一定是 GG 中的合法走法。

两边合起来

  Kmin⁡  =  ∑C: SC≠∅{∣TC∣/2∣TC∣>01∣TC∣=0  \boxed{\;K_{\min} \;=\; \sum_{C:\,S_C \ne \varnothing} \begin{cases} |T_C|/2 & |T_C| > 0\\ 1 & |T_C| = 0\end{cases}\;}

样例追踪。 题面样例里 SS 的边是 12→3412\to34 那一圈加三角形加 1111 附近两条边:

连通块 CC SCS_C 里各点的度数 TCT_C 人数
{1,2,3,4,5,6,7,8,9,10}\{1,2,3,4,5,6,7,8,9,10\} deg⁡1=1, 2=4, 3=2, 4=3, 5=1, 6=1, 7=2, 8=2, 9=2\deg 1=1,\ 2=4,\ 3=2,\ 4=3,\ 5=1,\ 6=1,\ 7=2,\ 8=2,\ 9=2 {1,4,5,6}\{1,4,5,6\} 4/2=24/2 = 2
{11,12,13}\{11,12,13\} deg⁡11=2, 12=1, 13=1\deg 11=2,\ 12=1,\ 13=1 {12,13}\{12,13\} 2/2=12/2 = 1

合计 K=3K=3,与样例输出第一行的 3 一致(样例给的走法也是一种最优方案)。

关于输出顺序:本题是特殊判题,但本地数据不是。 输出方案不唯一, 题面样例给的走法与本文代码给出的走法完全不同(两者都合法、都是 3 个人)。 不过本目录 data/*.out 是由参考实现跑出来的逐字节答案, check_sample.py 做的是整行 diff,所以 main.cpp / main.py 里刻意复刻了参考实现的构造顺序: 连通块按最小点编号编号、块内点按深搜出栈顺序编号、加边顺序统一为"树边 ×2 → SCS_C 边 → 虚点边"、 邻接表内按加边顺序遍历、欧拉回路从虚点出发后先走它邻接表里最早那条边。 真实数据 10/10 全过(见下文的验证记录)。真正上 ROJ 判题时输出顺序无所谓,任意合法方案都对。

数据来源说明。 素材源 new_ROJ/problems/1740/ 里带 data.py(cyaron 数据生成脚本), 且脚本里写着"未找到本题任何公开题解,标程系依据题面自研"。因此本题目面与数据都是重建的, 与官方原题的细节(例如是否允许重复点的走法、是否特殊判题)可能有偏差; 本文的推导只以 problem.md 的题面为准。素材源的 std.cpp 与题面一致: 它自带的结论与本文公式相同,实测它对 data/*.in 的输出与 data/*.out 逐字节相等 (说明数据本身自洽),本文的实现只是在写法上重写了一遍(去掉 lambda、改成全局数组)。

实现要点。

  • 手动模拟欧拉回路:用一张 CSR 邻接表 + "每个点下一个可取的位置"指针 cur[], 取不到未走过的边就把当前点压进答案栈并回退——这样不用递归,深度不受限。
  • 半边数组按"每条边两个半边、互为 twin"组织:走过一条半边时把 twin 一起标记, 保证每条边恰好被用一次。
  • 输出用 4MB 手动缓冲(KK 行、总长最多 1.5×1061.5 \times 10^6 个数),输入整块 fread 一次读入。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 22:05
# update_at: 2026-10-07 22:27

import sys

type Graph = tuple[list[int], list[int], list[int]]   # 原图 CSR:(区间表, 对端, 边号)
type Blocks = tuple[list[int], list[int], list[int], list[int]]  # (块号, 父边, 顶点序, 块区间表)


def build_graph(n: int, eu: list[int], ev: list[int]) -> Graph:
    """建原图 CSR 邻接:每个点的邻居按边的输入顺序排列(决定生成树与后续输出顺序)。"""
    off = [0] * (n + 1)
    for a in eu:
        off[a + 1] += 1
    for b in ev:
        off[b + 1] += 1
    for v in range(n):
        off[v + 1] += off[v]
    cur = off[:]                      # 每个点下一个可写的位置
    gto = [0] * (2 * len(eu))
    geid = [0] * (2 * len(eu))
    for i in range(len(eu)):
        a, b = eu[i], ev[i]
        p = cur[a]
        cur[a] = p + 1
        q = cur[b]
        cur[b] = q + 1
        gto[p], geid[p] = b, i
        gto[q], geid[q] = a, i
    return off, gto, geid


def find_blocks(n: int, graph: Graph) -> Blocks:
    """划分连通块,并顺带做深搜生成树:记录每个点的父边与块内出栈顺序。"""
    off, gto, geid = graph
    comp, par, order, beg = [-1] * n, [-1] * n, [], []
    ncomp = 0
    for s in range(n):
        if comp[s] != -1:
            continue
        beg.append(len(order))
        comp[s] = ncomp
        stack = [s]
        while stack:
            v = stack.pop()
            order.append(v)
            for p in range(off[v], off[v + 1]):
                to = gto[p]
                if comp[to] == -1:
                    comp[to] = ncomp
                    par[to] = geid[p]     # 父边 = 第一次发现这个点的那条边
                    stack.append(to)
        ncomp += 1
    beg.append(len(order))
    return comp, par, order, beg


def group_edges(m: int, ncomp: int, comp: list[int], eu: list[int]) -> tuple[list[int], list[int]]:
    """把边按所属连通块分组(计数排序,块内保持输入顺序),返回 (块区间表, 边的重排)。"""
    beg = [0] * (ncomp + 1)
    for i in range(m):
        beg[comp[eu[i]] + 1] += 1
    for c in range(ncomp):
        beg[c + 1] += beg[c]
    cur = beg[:]
    order = [0] * m
    for i in range(m):
        c = comp[eu[i]]
        order[cur[c]] = i
        cur[c] += 1
    return beg, order


def aux_edges(block: list[int], loc: list[int], par: list[int], eu: list[int], ev: list[int],
              s_edges: list[int], sdeg: list[int], n_odd: int) -> tuple[list[int], list[int]]:
    """辅助图 M 的边表 (ma, mb)。

    三条来源缺一不可:生成树的每条树边放 2 份(只为连通,不改奇偶)、块内所有 c=1 的边各 1 份、
    奇数度点各接一条连向虚点的边(虚点用块内编号 nC 表示)。
    """
    nC = len(block)
    ma: list[int] = []
    mb: list[int] = []
    for v in block:
        pe = par[v]
        if pe < 0:
            continue                       # 生成树的根没有父边
        u = ev[pe] if eu[pe] == v else eu[pe]
        lu, lv = loc[u], loc[v]
        ma.append(lu)
        mb.append(lv)
        ma.append(lu)
        mb.append(lv)
    for e in s_edges:
        ma.append(loc[eu[e]])
        mb.append(loc[ev[e]])
    if n_odd:
        for i, v in enumerate(block):
            if sdeg[v]:
                ma.append(nC)              # 虚点:切分路径的刀口
                mb.append(i)
    return ma, mb


def euler_seq(ma: list[int], mb: list[int], mvtx: int, base: int) -> list[int]:
    """迭代求 M 的欧拉回路,返回自 base 出发覆盖全边、首尾相同的顶点序列。"""
    me = len(ma)
    off = [0] * (mvtx + 1)
    for a in ma:
        off[a + 1] += 1
    for b in mb:
        off[b + 1] += 1
    for v in range(mvtx):
        off[v + 1] += off[v]
    cur = off[:]
    nbr = [0] * (2 * me)                   # 每条半边通向的对端
    twin = [0] * (2 * me)                  # 同一条边另一条半边的位置
    used = bytearray(2 * me)
    for i in range(me):
        a, b = ma[i], mb[i]
        p = cur[a]
        cur[a] = p + 1
        q = cur[b]
        cur[b] = q + 1
        nbr[p], nbr[q] = b, a
        twin[p], twin[q] = q, p
    ptr = off[:]
    seq: list[int] = []
    stack = [base]
    while stack:
        v = stack[-1]
        p = ptr[v]
        end = off[v + 1]
        while p < end and used[p]:
            p += 1
        if p == end:
            ptr[v] = end       # 剩余半边全走过:回退过的旧位置不再重复扫描(否则退化成 O(deg^2))
            seq.append(v)
            stack.pop()
        else:
            ptr[v] = p + 1
            used[p] = 1
            used[twin[p]] = 1
            stack.append(nbr[p])
    seq.reverse()
    return seq


def path_line(seg: list[int], block: list[int]) -> str:
    """把一段局部编号渲染成题目要求的一行:`l v1 v2 ... vl`(编号换回原图的 1 起)。"""
    return ' '.join([str(len(seg))] + [str(block[x] + 1) for x in seg])


def solve_case(n: int, m: int, eu: list[int], ev: list[int], ec: list[int]) -> list[str]:
    """一组数据的全部输出行:第一行是人数 K,之后是每个人走过的路径。"""
    sdeg = [0] * n                         # sdeg[v]:与 v 相邻的 c=1 边数 mod 2
    for a, b, ci in zip(eu, ev, ec):
        sdeg[a] ^= ci
        sdeg[b] ^= ci

    graph = build_graph(n, eu, ev)
    comp, par, order, vbeg = find_blocks(n, graph)
    ncomp = len(vbeg) - 1
    ebeg, eord = group_edges(m, ncomp, comp, eu)
    has_s = [False] * ncomp
    for i in range(m):
        if ec[i]:
            has_s[comp[eu[i]]] = True

    total_k = 0                            # 答案下界 = 每块奇数度点数 / 2,无奇数度点也要 1 趟
    for c in range(ncomp):
        if not has_s[c]:
            continue
        n_odd = sum(1 for v in order[vbeg[c]:vbeg[c + 1]] if sdeg[v])
        total_k += n_odd // 2 if n_odd else 1

    out = [str(total_k)]
    loc = [0] * n                          # 原图点 -> 块内局部编号
    for c in range(ncomp):
        if not has_s[c]:
            continue
        block = order[vbeg[c]:vbeg[c + 1]]
        for i, v in enumerate(block):
            loc[v] = i
        n_odd = sum(1 for v in block if sdeg[v])
        s_edges = [eord[k] for k in range(ebeg[c], ebeg[c + 1]) if ec[eord[k]]]
        ma, mb = aux_edges(block, loc, par, eu, ev, s_edges, sdeg, n_odd)
        nC = len(block)
        xv = nC if n_odd else 0            # 虚点:奇数度点成对时的拐点(编号 nC)
        mvtx = nC + 1 if n_odd else nC
        seq = euler_seq(ma, mb, mvtx, xv)
        if not n_odd:
            # 整块没有奇度点:这一整条回路就是 1 个人的走法(首点重复出现在末位)
            out.append(path_line(seq, block))
            continue
        prev = 0                           # seq[0] 就是虚点,两处虚点之间是 1 个人
        for i in range(1, len(seq)):
            if seq[i] != xv:
                continue
            if prev + 1 <= i - 1:          # 非空段才是一段真实路径
                out.append(path_line(seq[prev + 1:i], block))
            prev = i
    return out


def solve() -> None:
    vals = list(map(int, sys.stdin.buffer.read().split()))
    if not vals:
        return
    pos = 0
    T = vals[pos]
    pos += 1
    out: list[str] = []
    for _ in range(T):
        n, m = vals[pos], vals[pos + 1]
        pos += 2
        block = vals[pos:pos + 3 * m]      # 每 3 个数一条边:a, b, c
        pos += 3 * m
        eu = [x - 1 for x in block[0::3]]
        ev = [x - 1 for x in block[1::3]]
        ec = block[2::3]
        out += solve_case(n, m, eu, ev, ec)
    sys.stdout.write('\n'.join(out) + '\n')


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 22:05
 * update_at: 2026-10-07 22:27
 */
// main.cpp:一本通 1740《星空穿越》
// 题意:n 点 m 边的无向简单图,每条边带奇偶标记 c;用尽量少的行走使每条边被走过的总次数 ≡ c (mod 2)。
// 结论:设 S = {c=1 的边},对每个连通块 C 记 T_C = S∩C 中度数为奇数的点集,则
//       K_min = Σ_C ( |T_C| > 0 ? |T_C|/2 : [S_C 非空] )。
// 构造:块内取生成树、每条树边放 2 份(只加连通性、不改奇偶),再放入 S_C 的全部边;
//       若 T_C 非空,额外加一个虚点 X 与 T_C 各点相连,此时全图偶度且连通,
//       从 X 出发求欧拉回路,按 X 出现的位置切开,恰得 |T_C|/2 条路径。

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

typedef long long ll;

const int MAXN = 500005;    // 单组点数上限(题面 n ≤ 2×10^5,留足余量)
const int MAXM = 500005;    // 单组边数上限(题面 m ≤ 2×10^5,留足余量)
const int MAXME = 2000005;  // 辅助图 M 的边数上限:m + 2(n-1) + n 最坏约 2×10^6
const int MAXARC = 4000010; // M 的半边数上限
const int BUF_IN = 1 << 25; // 输入缓冲:整份数据一次读入(题面 Σn,Σm ≤ 5×10^5,最大约 10MB)
const int BUF_OUT = 1 << 22;

/* ── 输入:整块 fread + 手写整数解析 ── */
char in_buf[BUF_IN];
int in_len, in_pos;

inline int read_int() {
    if (in_pos >= in_len) return -1;
    int c = (unsigned char)in_buf[in_pos++];
    while (c <= ' ' && in_pos < in_len) c = (unsigned char)in_buf[in_pos++];
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        if (in_pos >= in_len) break;
        c = (unsigned char)in_buf[in_pos++];
    }
    return x;
}

/* ── 输出:整块缓冲 ── */
char out_buf[BUF_OUT];
int out_pos;

inline void out_flush() {
    if (out_pos) { fwrite(out_buf, 1, out_pos, stdout); out_pos = 0; }
}
inline void out_ch(char ch) {
    if (out_pos == BUF_OUT) out_flush();
    out_buf[out_pos++] = ch;
}
inline void out_int(ll x) {
    char tmp[24];
    int t = 0;
    if (x == 0) tmp[t++] = '0';
    while (x > 0) { tmp[t++] = (char)('0' + x % 10); x /= 10; }
    while (t > 0) out_ch(tmp[--t]);
}
inline void out_endl() { out_ch('\n'); }

/* ── 原图数据 ── */
int n, m;                      // 本组的点数与边数
int eu[MAXM], ev[MAXM], ec[MAXM]; // 第 i 条边:两端点(0 起)与奇偶标记
int sdeg[MAXN];                // sdeg[v] = 与 v 相邻的 S 边条数 mod 2

struct MEdge { int a, b; };    // 辅助图 M 的一条边(顶点为块内局部编号,虚点编号为 nC)

/* ── 原图 CSR 邻接:范围内按边的输入顺序排列,与生成树的遍历顺序一致 ── */
int g_off[MAXN + 1], g_to[2 * MAXM], g_eid[2 * MAXM];
int g_cur[MAXN];

/* ── 连通块与生成树 ── */
int comp[MAXN];                // 每个点所属连通块编号
int par_eid[MAXN];             // 生成树上每个点的父边编号(根为 -1)
int order_v[MAXN];             // 全部点按「连通块号 + 块内出栈顺序」排列
int vert_beg[MAXN + 1];        // 第 c 块的点占据 order_v[vert_beg[c], vert_beg[c+1])
int ncomp;

int eid_beg[MAXN + 1], eid_ord[MAXM], eid_cur[MAXN + 1]; // 边按连通块分组(块内保持输入顺序)
char has_s[MAXN];              // 第 c 块是否含有 c=1 的边

/* ── 辅助图 M:CSR 邻接 + 迭代欧拉回路 ── */
MEdge me[MAXME];
int m_off[MAXN + 1], m_cur[MAXN + 1];
int m_nbr[MAXARC], m_twin[MAXARC]; // 每条半边:对端顶点、镜像半边所在位置
char m_used[MAXARC];
int stack_v[MAXN];             // DFS 栈(原图)
int stack_e[MAXARC];           // 欧拉回路的 vertex 栈
int seq[MAXARC];               // 欧拉回路的顶点序列(逆序存放后原地反转)

int loc[MAXN], loc_vert[MAXN]; // 原图点 -> 块内局部编号;局部编号 -> 原图点
ll total_k;                    // 本组的答案 K

// 把一条边写进原图 CSR 边表的指定槽位(槽位由调用方按输入顺序分配)。
void fill_g_edge(int v, int eid, int pos) {
    g_to[pos] = v;
    g_eid[pos] = eid;
}

// 划分连通块并为每块记录出栈顺序、父边(决定生成树)。
void build_components() {
    ncomp = 0;
    int vcnt = 0;
    for (int s = 0; s < n; s++) {
        if (comp[s] != -1) continue;
        vert_beg[ncomp] = vcnt;
        comp[s] = ncomp;
        par_eid[s] = -1; // 生成树的根没有父边
        int sp = 0;
        stack_v[sp++] = s;
        while (sp) {
            int v = stack_v[--sp];
            order_v[vcnt++] = v;
            for (int p = g_off[v]; p < g_off[v + 1]; p++) {
                int to = g_to[p];
                if (comp[to] == -1) {
                    comp[to] = ncomp;
                    par_eid[to] = g_eid[p];
                    stack_v[sp++] = to;
                }
            }
        }
        ncomp++;
    }
    vert_beg[ncomp] = vcnt;
}

// 统计边的分组(按连通块)与每块是否含 S 边:两者都只扫描一遍边表。
void group_edges() {
    for (int c = 0; c <= ncomp; c++) eid_beg[c] = 0;
    for (int i = 0; i < m; i++) eid_beg[comp[eu[i]] + 1]++;
    for (int c = 0; c < ncomp; c++) eid_beg[c + 1] += eid_beg[c];
    for (int c = 0; c <= ncomp; c++) eid_cur[c] = eid_beg[c];
    for (int i = 0; i < m; i++) eid_ord[eid_cur[comp[eu[i]]]++] = i;
    for (int c = 0; c < ncomp; c++) has_s[c] = 0;
    for (int i = 0; i < m; i++)
        if (ec[i]) has_s[comp[eu[i]]] = 1;
}

// 迭代 Hierholzer:从 base 出发求 M 的欧拉回路,结果按逆序写进 seq 再原地反转。
void euler_circuit(int base, int mvtx, int &seq_cnt) {
    int sp = 0;
    seq_cnt = 0;
    for (int v = 0; v < mvtx; v++) m_cur[v] = m_off[v];
    stack_e[sp++] = base;
    while (sp) {
        int v = stack_e[sp - 1];
        int chosen = -1;
        while (m_cur[v] < m_off[v + 1]) {
            int p = m_cur[v]++;
            if (!m_used[p]) { chosen = p; break; } // 取 v 邻接表里第一条未走过的半边
        }
        if (chosen < 0) {                           // v 已经无路可走:记进回路并回退
            seq[seq_cnt++] = v;
            sp--;
        } else {
            m_used[chosen] = 1;
            m_used[m_twin[chosen]] = 1;             // 同一条边的两个方向一起标记
            stack_e[sp++] = m_nbr[chosen];
        }
    }
    for (int i = 0, j = seq_cnt - 1; i < j; i++, j--) {
        int t = seq[i]; seq[i] = seq[j]; seq[j] = t;
    }
}

// 输出第 c 块的一条路径:seq[l..r] 是块内局部编号,输出时换算回原图编号。
void print_path(int l, int r, int seq_cnt) {
    out_int(r - l + 1);
    for (int i = l; i <= r; i++) {
        out_ch(' ');
        out_int(loc_vert[seq[i]] + 1);
    }
    out_endl();
}

// 处理一个连通块:构造 M、求欧拉回路、切开输出。
void solve_comp(int c) {
    int beg = vert_beg[c], end = vert_beg[c + 1];
    int nC = end - beg;
    int nT = 0;
    for (int i = beg; i < end; i++) if (sdeg[order_v[i]]) nT++;
    if (!has_s[c]) return; // 该块没有任何 c=1 的边,不需要安排人

    for (int i = beg; i < end; i++) {
        loc[order_v[i]] = i - beg;
        loc_vert[i - beg] = order_v[i];
    }

    int me_cnt = 0;
    // (1) 生成树的每条树边放 2 份:既保证 M 连通,又不会改变任何点的度数奇偶
    for (int i = beg; i < end; i++) {
        int v = order_v[i];
        int pe = par_eid[v];
        if (pe < 0) continue;
        int u = (eu[pe] == v) ? ev[pe] : eu[pe];
        me[me_cnt].a = loc[u]; me[me_cnt].b = loc[v]; me_cnt++;
        me[me_cnt].a = loc[u]; me[me_cnt].b = loc[v]; me_cnt++;
    }
    // (2) S_C 的全部边各放 1 份:这就是必须被走成奇数次的那部分
    for (int k = eid_beg[c]; k < eid_beg[c + 1]; k++) {
        int i = eid_ord[k];
        if (!ec[i]) continue;
        me[me_cnt].a = loc[eu[i]]; me[me_cnt].b = loc[ev[i]]; me_cnt++;
    }
    // (3) 奇数度点各接一条虚点边:让虚点成为唯一"多出来"的拐点
    int xv = (nT > 0) ? nC : -1;
    if (xv >= 0) {
        for (int i = beg; i < end; i++)
            if (sdeg[order_v[i]]) { me[me_cnt].a = xv; me[me_cnt].b = i - beg; me_cnt++; }
    }

    // 建 M 的 CSR 邻接:半边 2i 落在第 i 条边 a 端的区间里,半边 2i+1 落在 b 端,
    // 每个顶点的邻接区间内保持边的构造顺序(与生成路径的顺序一致)。
    int mvtx = nC + (xv >= 0 ? 1 : 0);
    for (int v = 0; v <= mvtx; v++) m_off[v] = 0;
    for (int i = 0; i < me_cnt; i++) { m_off[me[i].a + 1]++; m_off[me[i].b + 1]++; }
    for (int v = 0; v < mvtx; v++) m_off[v + 1] += m_off[v];
    for (int v = 0; v <= mvtx; v++) m_cur[v] = m_off[v];
    for (int i = 0; i < me_cnt; i++) {
        int a = me[i].a, b = me[i].b;
        int p = m_cur[a]++, q = m_cur[b]++;
        m_nbr[p] = b; m_twin[p] = q;
        m_nbr[q] = a; m_twin[q] = p;
    }
    for (int i = 0; i < 2 * me_cnt; i++) m_used[i] = 0;

    int seq_cnt = 0;
    euler_circuit(xv >= 0 ? xv : 0, mvtx, seq_cnt);

    if (xv < 0) {
        // T_C = ∅:M 本身就是欧拉图,整条回路就是 1 条行走(首尾同点需要重复输出一次)
        out_int(seq_cnt);
        for (int i = 0; i < seq_cnt; i++) { out_ch(' '); out_int(loc_vert[seq[i]] + 1); }
        out_endl();
    } else {
        // T_C ≠ ∅:回路里每两次经过虚点之间就是一条路径,虚点自身不输出
        int prev = 0; // seq[0] == 虚点
        for (int i = 1; i < seq_cnt; i++) {
            if (seq[i] != xv) continue;
            if (prev + 1 <= i - 1) print_path(prev + 1, i - 1, seq_cnt);
            prev = i;
        }
    }
}

int main() {
    in_len = (int)fread(in_buf, 1, sizeof(in_buf), stdin);
    in_pos = 0;
    int T = read_int();
    if (T < 0) { out_flush(); return 0; }

    for (int tc = 0; tc < T; tc++) {
        n = read_int();
        m = read_int();
        for (int v = 0; v < n; v++) { comp[v] = -1; sdeg[v] = 0; g_off[v] = 0; }
        g_off[n] = 0;

        for (int i = 0; i < m; i++) {
            int a = read_int() - 1, b = read_int() - 1, c = read_int();
            eu[i] = a; ev[i] = b; ec[i] = c;
            sdeg[a] ^= c; sdeg[b] ^= c; // 度数的奇偶:每条相邻的 S 边各翻转一次
        }

        // 原图 CSR:先数度数,再按边的输入顺序填边表
        for (int i = 0; i < m; i++) { g_off[eu[i] + 1]++; g_off[ev[i] + 1]++; }
        for (int v = 0; v < n; v++) g_off[v + 1] += g_off[v];
        for (int v = 0; v < n; v++) g_cur[v] = g_off[v];
        for (int i = 0; i < m; i++) {
            int p = g_cur[eu[i]]++, q = g_cur[ev[i]]++;
            fill_g_edge(ev[i], i, p);
            fill_g_edge(eu[i], i, q);
        }

        build_components();
        group_edges();

        // 第一遍:只算答案 K
        total_k = 0;
        for (int c = 0; c < ncomp; c++) {
            if (!has_s[c]) continue;
            int nT = 0;
            for (int i = vert_beg[c]; i < vert_beg[c + 1]; i++)
                if (sdeg[order_v[i]]) nT++;
            total_k += (nT > 0) ? (nT / 2) : 1;
        }
        out_int(total_k); out_endl();

        // 第二遍:逐块构造并输出路径
        for (int c = 0; c < ncomp; c++) {
            if (!has_s[c]) continue;
            solve_comp(c);
        }
    }

    out_flush();
    return 0;
}

复杂度

  • 时间:连通块划分、生成树、按块分组边、建 MCM_C、欧拉回路各是 O(n+m)O(n+m), 切开并输出也是 O(n+m)O(n+m),所以单组 O(n+m)O(n+m),总体 O(∑n+∑m)O(\sum n + \sum m)。 ∑n,∑m≤5×105\sum n, \sum m \le 5\times 10^5,限时 2000 ms 富余很大(实测 C++ 最大测试点 0.11 s)。
  • 空间:原图 CSR O(n+m)O(n+m),辅助图 MM 的边数不超过 m+2(n−1)+nm + 2(n-1) + n, 与其半边数组同阶,O(n+m)O(n+m);C++ 侧全局数组按上界静态开好,实测峰值 RSS 约 54 MB(限 512 MB)。
  • 输出长度:∑ili≤∣S∣+2∑n+K≈1.5×106<5×106\sum_i l_i \le |S| + 2\sum n + K \approx 1.5\times 10^6 < 5\times 10^6, 满足题面"ll 之和不超过 5×1065\times 10^6"的要求。
  • 与 C++ 解法的关系:main.py 与 main.cpp 是同一算法的两套写法, 连"加边顺序 / 邻接表内顺序"都一致,因此输出逐字节相同;Python 版慢在常数, 算法阶数完全相同,不存在把构造退化成暴力搜索的情况。本机实测 main.py 每个测试点 0.02 s ~ 1.44 s(最大的两组约 1.0 s / 1.4 s),已逼近 2000 ms 的限制, 在更慢的评测机上有 TLE 风险(本仓库规范允许 Python TLE,算法不降级); 另外 Python 的欧拉回路必须先 ptr[v] = end 再回退,否则同一个死点会被反复扫描尾段, 退化成 O(deg⁡2)O(\deg^2)(实测 2 万点星形从 0.05 s 变成 6.3 s)。

总结

  • 只看奇偶就别管具体次数:把"走若干次"压成 F2\mathbb{F}_2 上的边集异或, 奇度顶点集 ∂\partial 是线性映射,于是"最少几个人"立刻被 ∣TC∣≤2k|T_C| \le 2k 卡住。
  • 允许折返是本题的题眼:因为走法可以有重复边,一次行走的奇偶边集可以不连通 (靠 c=0c=0 的边来回走两次拼接),所以"每个 SS 连通块一个人"是错的下界, 真正的下界只有奇数度点数的一半。
  • 构造靠"生成树双份 + 虚点":双份树边把整块连起来又不改奇偶, 虚点把 ∣TC∣|T_C| 个奇度点两两配对,欧拉回路按虚点切开就是最优方案, 输出长度还是 O(n+m)O(n+m) 级别。
  • 特殊判题的题也要盯输出格式:ll 必须等于该行顶点个数、l>0l>0、编号在 1…n1 \dots n 内, 总长不能爆;本地比对若是逐字节 diff,就必须把构造顺序也固定下来。