学习目标
前置知识与环境
先阅读DFS 与 BFS 基础。需要 C++17 编译器，运行前可执行 make doctor。
题目
判断无向多重图能否不重复地走遍所有边。所有非零度顶点必须属于同一连通分量，孤立顶点不影响结论。每个自环对度数贡献 2。优先判断欧拉回路；若恰有两个奇度顶点，则有欧拉路径，起点固定为较小的奇度顶点。没有边时约定存在长度为 0 的欧拉回路。
输入格式
第一行 n m，随后 m 行 u v。1 ≤ n ≤ 10000，0 ≤ m ≤ 100000，顶点 0..n-1；允许自环、重边、非连通图。
输出格式
存在回路输出 Eulerian Circuit；仅存在路径输出 Eulerian Path s（同一行）；其余输出 Not Eulerian。
样例输入
input
3 3
0 1
1 2
2 0样例输出
output
Eulerian Circuit样例解释
三个非零度顶点连通且度数均为 2，因此存在欧拉回路。
任务
- 统计度数，自环必须计算两次。
- 从最小非零度顶点检查所有有边顶点的连通性。
- 结合奇度数输出分类和规范起点。
在 student/main.cpp 的 TODO 处完成算法。起始代码可以编译，但不代表已经实现题目；参考实现位于 solution/main.cpp。
正常、边界与错误情况
只有偶度条件不够：两个互不连通的环仍然不可一笔画。
输入保证符合上述格式与范围，不要求处理损坏输入。无解、不可达等情况按本题输出合同处理，不视为格式错误。测试点包含如下场景，每点 5 分，共 100 分：
| 测试点 | 类型 |
|---|---|
001-sample | 样例 |
002-singleton-empty | 边界 |
003-many-isolated | 边界 |
004-isolated-zero | 易错反例 |
005-two-disconnected-cycles | 易错反例 |
006-two-odd | 易错反例 |
007-four-odd | 易错反例 |
008-seven-bridges | 易错反例 |
009-self-loop | 易错反例 |
010-parallel-bridges | 易错反例 |
011-bridge-must-be-spliced | 易错反例 |
012-disconnected-loops | 易错反例 |
013-seeded-walk-0 | 正常 |
014-seeded-walk-1 | 正常 |
015-seeded-walk-2 | 正常 |
016-seeded-walk-3 | 正常 |
017-seeded-walk-4 | 正常 |
018-long-chain | 规模 |
019-many-parallel | 规模 |
020-max-vertices-isolated | 规模 |
运行与评分
在本 Lab 目录执行：
powershell
make doctor
make run CASE=001-sample
make score未安装 Make 时，在仓库根目录执行：
powershell
pnpm lab:doctor -- labs/chapter-07/exercise/E-07-04-eulerian-classification
pnpm lab:run -- labs/chapter-07/exercise/E-07-04-eulerian-classification --case 001-sample
pnpm lab:score -- labs/chapter-07/exercise/E-07-04-eulerian-classification解题思路
无向图存在欧拉回路当且仅当所有非孤立顶点属于同一连通分量且每个顶点度数为偶数。统计度数时自环贡献两次，再从任意非孤立顶点 DFS 检查连通性。
复杂度分析
连通性与度数检查 O(n+m) 时间，邻接表 O(n+m) 空间。
完成清单
思考与复盘
- 本题最容易遗漏的约束是什么？
参考思路
只有偶度条件不够：两个互不连通的环仍然不可一笔画。
- 为什么“所有顶点度数为偶数”仍不足以保证欧拉回路？请构造一个不连通反例，并说明程序如何排除它。
参考思路
两个互不连通的环中每个顶点都是偶度，但无法用一条路线走完两部分。程序应从任意非孤立顶点 DFS，并检查所有非零度顶点是否都被访问。