返回题目列表
COMP2521
欧拉 · 数奇数度顶点
欧拉 · 数一数有几个奇数度顶点
判断「能否一笔画」的关键量,就是奇数度顶点的个数。读入一张无向图,输出有多少个顶点的度数是奇数。
请补全:先用每条边给两端顶点的度数各 +1,再数有几个度数为奇数。
提示:无向边u–v让deg[u]++且deg[v]++。最后deg[i] % 2 == 1的就是奇点。
小知识:由「握手定理」,奇数度顶点的个数<strong>一定是偶数</strong>(0、2、4…)。
输入
- 第 1 行:
V E(顶点数、边数)。 - 接下来
E行:u v,一条无向边(E可能为 0)。
输出
- 一行:奇数度顶点的个数。
示例:输入 4 3 / 0 1 / 1 2 / 2 3 → 输出 2(顶点 0、3 各 1 度,是奇点;1、2 各 2 度)。
样例
stdin
4 3 0 1 1 2 2 3
期望输出
2
stdin
4 4 0 1 1 2 2 3 3 0
期望输出
0
c-dcc
14