返回题目列表
COMP2521
图 · 最大出入度差 maxDegreeDiff
图 · 最大出入度差(2521 24T2 真题)
读入一张有向图:顶点 0 … V-1,E 条有向边(u v 表示 u → v)。对每个顶点 i,算出它的出度(从 i 出发的边数)和入度(指向 i 的边数),输出所有顶点中 |出度 − 入度| 的最大值。
请补全 maxDegreeDiff。
易错点(正是错误实验室里的坑):出度和入度<strong>方向相反</strong>——u → v时,u的出度 +1、v的入度 +1,别数反了。最后取的是<strong>绝对值</strong>的最大值(差可正可负)。
输入
- 第 1 行:
V E。 - 接下来
E行:每行u v,表示有向边u → v。
输出
- 一行:所有顶点中
|出度 − 入度|的最大值(图为空或无边时为0)。
示例:输入 4 3 / 0 1 / 0 2 / 0 3 → 输出 3(顶点 0 出度 3、入度 0,差 3 最大)。
样例
stdin
4 3 0 1 0 2 0 3
期望输出
3
stdin
3 3 0 1 1 2 2 0
期望输出
0
c-dcc
14