题目来源：本 Lab 提取了 LeetCode 2508：添加边使所有节点度数都为偶数所需的度数与奇偶性统计能力，并扩展到有向图、自环和平行边。原题还要求判断能否添加至多两条边，这部分分类讨论不属于本 Lab 的自动评分范围。
学习目标
前置知识
开始前先阅读 6.1 图的基本概念中的“邻接与度”部分，并准备支持 C++17 的编译器；可运行 make doctor 检查环境。
题目
给定一张无向图或有向图，逐条读取边并统计每个顶点的度数。输入可能包含自环和平行边，因此不能把边去重，也不能把无向自环只计算一次。
- 无向图中，普通边在两个端点处各贡献一次度，自环在同一顶点处贡献两次度；
- 有向图中，边
u → v为u贡献一次出度、为v贡献一次入度；有向自环同时贡献一次入度和一次出度； - 输入中的每条平行边都应作为独立边分别计数。
输入格式
第一行包含一个字符 type 和两个整数 n m：
type为U表示无向图，为D表示有向图；n为顶点数，顶点编号为0到n-1；m为边数。
接下来 m 行，每行包含两个整数 u v。在无向图中表示边 {u,v}，在有向图中表示边 u → v。输入保证：
1 <= n <= 100000；0 <= m <= 200000；0 <= u, v < n；- 允许自环和平行边；
type一定是U或D，无需处理非法格式。
输出格式
无向图
输出两行：
- 第一行输出
n个整数degree[0] ... degree[n-1]； - 第二行输出两个整数，依次为度数总和与奇数度顶点数量。
无向图样例
input
U 4 4
0 1
0 3
1 2
2 2output
2 2 3 1
8 2自环 {2,2} 为顶点 2 的度贡献 2，所以度数和仍为 2m = 8。
有向图
输出三行：
- 第一行输出
n个整数，依次为各顶点的入度； - 第二行输出
n个整数，依次为各顶点的出度； - 第三行输出两个整数，依次为入度总和与出度总和。
有向图样例
input
D 4 4
0 1
0 2
2 1
1 3output
0 2 1 1
2 1 1 0
4 4任务
- 根据
type分配无向度数数组，或有向入度、出度数组； - 读取每条边并立即更新相应计数，不保存完整邻接矩阵；
- 无向自环必须执行一次
degree[u] += 2； - 统计并输出校验量：无向图输出度数和与奇数度顶点数，有向图输出入度和与出度和。
正常、边界与错误情况
| 情况 | 预期行为 |
|---|---|
| 普通无向图 | 每条非自环边为两个端点各贡献一次度，度数和为 2m |
| 普通有向图 | 每条边贡献一次入度和一次出度，两种总和都为 m |
| 无向自环 | 在同一顶点处贡献两次度 |
| 有向自环 | 在同一顶点处分别贡献一次入度和一次出度 |
| 平行边 | 每条边分别计数，不去重 |
| 无边图 | 所有计数与校验量均为 0 |
| 非连通图和孤立顶点 | 不影响统计；孤立顶点对应计数为 0 |
| 越界顶点或非法类型 | 自动评分输入不会出现；不要向标准输出添加提示或错误信息 |
运行与评分
在本 Lab 目录执行：
powershell
make doctor
make run
make run CASE=001-undirected-sample
make score未安装 Make 时，在仓库根目录执行：
powershell
pnpm lab:doctor -- labs/chapter-06/exercise/E-06-01-graph-degree-statistics
pnpm lab:run -- labs/chapter-06/exercise/E-06-01-graph-degree-statistics
pnpm lab:score -- labs/chapter-06/exercise/E-06-01-graph-degree-statistics完成清单
复杂度分析
读取并处理每条边需要 O(m) 时间，输出和汇总 n 个顶点需要 O(n) 时间，总时间复杂度为 O(n+m)。无向图只保存一个长度为 n 的度数数组，有向图保存入度和出度两个数组，空间复杂度均为 O(n)。
思考与复盘
- 为什么无向自环必须为同一个顶点的度增加
2，而有向自环只为入度和出度各增加1？ - 为什么平行边不能在本题中去重？去重后，哪些关于输入边数
m的校验等式会立刻暴露问题？ - 奇数度顶点数量为什么一定是偶数？这与度数和为偶数有什么关系？
- LeetCode 2508 为什么只需要重点考察奇数度顶点？如果奇数度顶点超过四个，为什么添加至多两条边一定不够？