「一本通 3.7 练习 2」Ant Trip

题目描述

给定无向图的 $N$ 个点和 $M$ 条边（无重边、无自环），多组数据用空行隔开。每组数据第一行两个整数 $N,M$ ，接下来 $M$ 行每行两个整数 $a,b$ 表示一条边。求最少几笔能把所有边画一遍，每笔不能离开纸且边不重复。孤立点无需遍历。

思路

含边连通块各自独立。若某连通块有 $k$ 个奇度顶点，则 $k=0$ 时一笔（欧拉回路），否则至少且恰好需要 $\frac{k}{2}$ 笔。用并查集维护连通块，统计每个点的度数和每个含边连通块的奇度点数即可。

参考代码

Python 版：

python

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
83
84
85
86
87
88
89
90
91
92#!/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-09-28 17:00
# update_at: 2026-09-28 17:00

import sys


def find(parent: list[int], x: int) -> int:
    """带路径压缩的并查集查找代表元。"""
    root = x
    while parent[root] >= 0:
        root = parent[root]
    curr = x
    while curr != root:
        nxt = parent[curr]
        if nxt < 0:
            break
        parent[curr] = root
        curr = nxt
    return root


def union(parent: list[int], x: int, y: int) -> None:
    """按秩合并两个集合。"""
    rx = find(parent, x)
    ry = find(parent, y)
    if rx == ry:
        return
    if parent[rx] < parent[ry]:  # rx 集合更大（负数绝对值更大）
        parent[rx] += parent[ry]
        parent[ry] = rx
    else:
        parent[ry] += parent[rx]
        parent[rx] = ry


def min_strokes_for_graph(n: int, edges: list[tuple[int, int]]) -> int:
    """计算遍历图中所有边所需的最少笔数。"""
    if not edges:
        return 0

    parent = [-1] * (n + 1)
    degree = [0] * (n + 1)

    for u, v in edges:
        degree[u] += 1
        degree[v] += 1
        union(parent, u, v)

    odd_counts: dict[int, int] = {}
    active_roots: set[int] = set()

    for i in range(1, n + 1):
        if degree[i] > 0:
            root = find(parent, i)
            active_roots.add(root)
            if degree[i] & 1:
                odd_counts[root] = odd_counts.get(root, 0) + 1

    total_strokes = sum(
        odd_counts[root] // 2 if odd_counts.get(root, 0) > 0 else 1
        for root in active_roots
    )
    return total_strokes


def solve() -> None:
    input_data = sys.stdin.buffer.read().split()
    if not input_data:
        return
    data_iter = iter(input_data)
    out: list[str] = []

    while True:
        try:
            n = int(next(data_iter))
            m = int(next(data_iter))
        except StopIteration:
            break

        edges = [(int(next(data_iter)), int(next(data_iter))) for _ in range(m)]
        ans = min_strokes_for_graph(n, edges)
        out.append(str(ans))

    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * 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-06 00:35
 * update_at: 2026-10-06 00:35
 */
#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

int fa[MAXN];       // 并查集父节点
int deg[MAXN];      // 每个点的度数
int odd[MAXN];      // odd[root] 表示该连通块中奇度点的个数
bool has_edge[MAXN]; // 标记该点是否在某个含边连通块中出现过

// 并查集查找
int find_fa(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find_fa(fa[x]);
}

// 并查集合并
void unite(int x, int y) {
    int fx = find_fa(x);
    int fy = find_fa(y);
    if (fx != fy) fa[fx] = fy;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    // 多组数据，按输入流直到结束
    while (cin >> n >> m) {
        // 初始化
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
            deg[i] = 0;
            odd[i] = 0;
            has_edge[i] = false;
        }

        for (int i = 1; i <= m; i++) {
            int a, b;
            cin >> a >> b;
            deg[a]++;
            deg[b]++;
            unite(a, b);
        }

        // 统计每个含边连通块的奇度点数量
        for (int i = 1; i <= n; i++) {
            if (deg[i] == 0) continue; // 忽略孤立点
            int root = find_fa(i);
            has_edge[root] = true;
            if (deg[i] % 2 == 1) odd[root]++;
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (!has_edge[i]) continue;
            if (odd[i] == 0) ans += 1;
            else ans += odd[i] / 2;
        }

        cout << ans << "\n";
    }

    return 0;
}

「一本通 3.7 练习 2」Ant Trip

目录

题目描述

思路

参考代码