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