「一本通 3.7 练习 1」欧拉回路

形式化题目

给定若干个无向图，第 $i$ 个图有 $N$ 个顶点（ $1 < N < 1000$ ，顶点编号 $1 \sim N$ ）与 $M$ 条边，允许重边与自环。对每个图回答：

是否存在一条经过图中每条边恰好一次、并且回到出发点的闭合通路（欧拉回路）？

存在输出 1，否则输出 0。输入含多组数据，以单独一行的 $N = 0$ 结束。

题面没有禁止自环与重边，实际测试数据里两者都出现过（例如某组数据的三条边是 1 1、2 2、3 3，另一组里 1 2 出现了两次）。它们是合法的普通边，判定时必须一并处理。

正解

思路

本题只问「存在性」，不要求输出回路，所以不必真的走一遍（Hierholzer 构造回路反而更慢、更容易写错），只要验证欧拉回路存在的两个必要条件是否也是充分的。

无向图欧拉回路判定定理：图 $G$ 存在欧拉回路，当且仅当

度数条件： $G$ 中每个顶点的度数都是偶数；
连通条件：所有含边的顶点属于同一个连通块。

为什么度数必须全偶。 欧拉回路经过某个顶点 $v$ 时，总是「从一条边进来、从另一条边出去」成对消耗 $v$ 的边；起点/终点同一个点，它额外消耗的边也是成对的。所以回路把 $v$ 的边两两配对用完， $\deg(v)$ 必为偶数。

为什么有边的点必须连通。 一笔画不能抬笔，若边分散在两个互不相通的连通块里，走完一块后无法到达另一块。

为什么这两条已经够。 若度数全偶，从任一含边的顶点出发，贪心地沿未用边行走：假设走到 $v$ 时无路可走，则 $v$ 的边都已用过，而已用边中与 $v$ 关联的条数是奇数（每次「进入」配一次「离开」，唯独最后停在 $v$ 的那次没有配对），与 $\deg(v)$ 为偶数矛盾。因此行走一定不会中途卡死，必然回到起点，形成一条回路。若这条回路没覆盖全部边，由连通性知回路外必有一条边与回路共用一个顶点，从该顶点出发又能走出新回路，把两条回路在该顶点拼接即可；重复拼接直到覆盖所有边。故两条条件也是充分的。

怎么检查这两条条件。

度数：读入每条边 $(u, v)$ 时 deg[u]++、deg[v]++。自环 $(v, v)$ 会执行两次自增，正好给 $v$ 记 $2$ 度，无需特判；重边各加一次，也无需特判。
连通性：用并查集把每条边的两个端点合并，最后统计度数大于 $0$ 的顶点里有多少个不同的并查集根。根超过一个说明边被分到了多个连通块，答案为 0。
孤立点不能参与连通性统计：度数为 $0$ 的点压根不碰边，把它算进去会把本来合法的图误判为不连通。例如样例中 $N = 4$ 而只有三角形 $1\text{-}2\text{-}3$ 的三条边时，点 $4$ 是孤立点，答案仍是 1。

以题面样例为例。第一组的三条边是 $1\text{-}2$ 、 $1\text{-}3$ 、 $2\text{-}3$ ，构成一个三角形：

graph LR
    A((1)) --- B((2))
    A --- C((3))
    B --- C

三个点的度数都是 $2$ ，且它们连成一片，两个条件都满足，输出 1。

第二组的两条边是 $1\text{-}2$ 、 $2\text{-}3$ ，是一条链：

graph LR
    D((1)) --- E((2)) --- F((3))

点 $1$ 与点 $3$ 的度数都是 $1$ （奇数），度数条件不满足，输出 0。

代码

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#!/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 15:13
# update_at: 2026-10-07 15:13

import sys
from collections.abc import Iterator


def find_root(fa: list[int], x: int) -> int:
    """并查集找根，带路径压缩。"""
    while fa[x] != x:
        fa[x] = fa[fa[x]]
        x = fa[x]
    return x


def has_euler_circuit(n: int, m: int, data: Iterator[int]) -> bool:
    """读入一个样例的 m 条边，判断这张图是否存在欧拉回路。"""
    deg = [0] * (n + 1)      # deg[v] = 点 v 的度数；自环 (v,v) 给 v 记 2 度
    fa = list(range(n + 1))  # 并查集，只用来判断「有边的点」是否连成一片

    for _ in range(m):
        u, v = next(data), next(data)
        deg[u] += 1
        deg[v] += 1
        root_u, root_v = find_root(fa, u), find_root(fa, v)
        if root_u != root_v:
            fa[root_u] = root_v

    if any(d % 2 for d in deg[1:]):  # 条件一：所有点的度数都是偶数
        return False
    # 条件二：度数为正的顶点里并查集根只有一个；一条边都没有时 0 个，也算连通
    roots = {find_root(fa, v) for v in range(1, n + 1) if deg[v]}
    return len(roots) <= 1


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    for n in data:  # 每个样例的第一个数就是 N，读到 0 表示输入结束
        if n == 0:
            break
        m = next(data)
        out.append("1" if has_euler_circuit(n, m, data) else "0")
    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/**
 * 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 15:13
 * update_at: 2026-10-07 15:13
 */
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll MAXN = 1005;  // 节点数上限：题面给的是 1 < N < 1000

ll n, m;       // 当前测试样例的节点数、边数
ll deg[MAXN];  // deg[v] = 点 v 的度数；自环 (v,v) 给 v 贡献 2 度
ll fa[MAXN];   // 并查集父亲数组，只用来判断「有边的点」是否连成一片

// 并查集找根，带路径压缩（写成循环，避免深递归）
ll find_root(ll x) {
    ll root = x;
    while (fa[root] != root) root = fa[root];
    while (fa[x] != root) {
        ll nxt = fa[x];
        fa[x] = root;
        x = nxt;
    }
    return root;
}

// 合并两个点所在的集合
void union_set(ll a, ll b) {
    ll ra = find_root(a);
    ll rb = find_root(b);
    if (ra != rb) fa[ra] = rb;
}

// 判断当前这张图是否存在欧拉回路（deg 和 fa 已由 main 填好）
bool has_euler_circuit() {
    // 条件一：所有点的度数都是偶数，否则一笔画必然回不到起点
    for (ll v = 1; v <= n; v++) {
        if (deg[v] % 2 != 0) return false;
    }

    // 条件二：所有「有边相连」的点必须落在同一个连通块里
    // 数一数度数为正的顶点里有几个并查集根，超过一个说明边分散在多块中
    ll root_cnt = 0;
    for (ll v = 1; v <= n; v++) {
        if (deg[v] == 0) continue;  // 孤立点不参与连通性判断，直接跳过
        if (find_root(v) == v) root_cnt++;
    }
    return root_cnt <= 1;  // 一条边都没有时 root_cnt 为 0，视作存在空回路
}

int main() {
    while (scanf("%lld", &n) == 1 && n != 0) {  // 读到 N 为 0 时输入结束
        scanf("%lld", &m);

        for (ll v = 1; v <= n; v++) {
            deg[v] = 0;  // 每个样例重新清空度数和并查集
            fa[v] = v;
        }

        for (ll i = 1; i <= m; i++) {
            ll u, v;
            scanf("%lld %lld", &u, &v);
            deg[u]++;
            deg[v]++;         // 无向边：两个端点各加一度
            union_set(u, v);  // 把这条边的两个端点并入同一个集合
        }

        printf("%d\n", has_euler_circuit() ? 1 : 0);
    }
    return 0;
}

复杂度

时间复杂度：单个测试样例读入 $M$ 条边、合并 $M$ 次并查集，再做 $O(N)$ 次度数检查与找根，总计 $O(M\,\alpha(N) + N)$ ，其中 $\alpha$ 是并查集的反阿克曼函数，实际接近常数；所有样例相加即为总复杂度。
空间复杂度：度数数组与并查集数组各 $O(N)$ ，且无需存储任何边，空间为 $O(N)$ （C++ 侧固定开 $1005$ 大小的全局数组，Python 侧按 $N$ 现开）。

总结

欧拉回路存在性判定是「度数条件 + 连通条件」两个独立检查的组合，缺一不可：只查度数会把「两个各自成环的三角形」判成有解，只查连通会把链判成有解。实现上要记住三点：

自环与重边都是普通边，自环给端点贡献 $2$ 度，不需要特判；
连通性只统计有边的点，孤立点必须跳过；
本题只要回答「有没有」，不要为了「输出回路」去做 Hierholzer，白白增加实现量和常数。

「一本通 3.7 练习 1」欧拉回路

目录

形式化题目

正解

思路

代码

复杂度

总结