← 返回题目列表

AtCoder · awc0035_c

C. 连锁停电

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥管理某个地区的电网。这个电网有 N 变电站,编号自 1 to N.

有 M 变电站之间铺设的输电线路。传输线 k (1 \leq k \leq M) 从变电站方向供电 U_k 至变电站 V_k。不存在自循环(U_k \neq V_k)。另外,相同的有序对 (U_k, V_k) 不会出现多次。然而,对于两个变电站 u, v,有可能来自变电站的传输线 u 至变电站 v 和来自变电站的传输线 v 至变电站 u 同时存在。

各变电站 i (1 \leq i \leq N)有一个 耐久值 T_i。另外,各变电站 i 有一个非负整数值,称为其 负载。初始阶段,所有变电站均投入运行,变电站负荷 i 等于电力流入变电站的输电线路的数量 i,即传输线数 k 满意 V_k = i (变电站入度 有向图中的 i )。

在该电网中,当变电站的负荷超过其耐久值时,就会发生停电,并且可能会连锁反应蔓延。具体流程如下。

请注意 已经经历过停电的变电站的负载在之后不会发生变化。

  1. 停电发生: 尚未停电的变电站中,是否存在负荷 严格超过 其耐久值(即对于变电站 j,负载 > T_j),选择其中任意一项。设所选变电站为变电站 s。如果不存在这样的变电站,则链结束。
  2. 停电处理: 变电站 s 遇到停电并停止运行。由于变电站送电 s 被切断,每个目的地变电站试图通过其他路线补偿损失的电力,导致负载增加。具体来说,对于每条传输线 k 这样 U_k = s,如果目的地变电站 V_k 尚未经历停电,变电站负荷 V_k 增加 1 (已经停电的变电站负荷不变)。
  3. 重复: 返回步骤 1。

由于变电站的数量是有限的,因此该链始终以有限数量的步骤终止。

注意: 可以证明,当多个变电站满足步骤1的条件时,无论选择哪个变电站,最终发生停电的变电站集合都是相同的。因此,答案是唯一确定的。

当链完全稳定后(即,当尚未发生停电的变电站均没有严格超过其耐久值的负载时),查找最终发生停电的所有变电站号。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq T_i \leq N (1 \leq i \leq N)
  • 1 \leq U_k \leq N (1 \leq k \leq M)
  • 1 \leq V_k \leq N (1 \leq k \leq M)
  • U_k \neq V_k (1 \leq k \leq M)
  • 相同的有序对 (U_k, V_k) 出现次数不超过一次
  • 所有输入值均为整数

输入

N M
T_1 T_2 \ldots T_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 第一行包含变电站的数量 N 和传输线的数量 M,用空格分隔。
  • 第二行包含耐久性值 每个变电站的 T_1, T_2, \ldots, T_N ,以空格分隔。
  • 如下 M 行, k- 第行 (1 \leq k \leq M) 包含 U_k 和 V_k 以空格分隔,代表传输线路信息 k。这意味着有一条输电线路从变电站供电 U_k 至变电站 V_k.

输出

在一行中按升序输出最终停电的所有变电站的编号,并以空格分隔。如果没有变电站发生停电,则输出 -1 代替。


示例输入 1

5 5
0 1 1 1 1
1 2
1 3
2 3
3 4
4 5

示例输出 1

3 4 5

示例输入 2

3 2
0 1 1
1 2
1 3

示例输出 2

-1

示例输入 3

7 9
0 1 1 1 1 2 2
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
2 6

示例输出 3

4 5 6 7

示例输入 4

10 12
0 1 1 1 1 1 1 1 2 1
1 2
1 3
2 3
3 4
3 5
4 6
5 6
6 7
6 8
7 9
8 9
9 10

示例输出 4

3 4 5 6 7 8 9 10

示例输入 5

1 0
0

示例输出 5

-1