OlveraeUNSW
返回题目列表
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