Peaks

题目描述

AtCoder 山上有 $N$ 个天文台，称为 Obs. $1$、Obs. $2$、...、Obs. $N$。天文台 $i$ 的海拔是 $H_i$。 还有 $M$ 条道路，每条道路连接两个不同的天文台。道路 $j$ 连接 Obs. $A_j$ 和 Obs. $B_j$。 当从 Obs. $i$ 出发仅使用一条道路就能到达的所有天文台的海拔都低于 Obs. $i$ 的海拔时，称 Obs. $i$ 为良好（good）。 注意，当从 Obs. $i$ 出发没有任何天文台可通过一条道路到达时，Obs. $i$ 也被视为良好。 良好的天文台有多少个？

输入格式

输入按下述格式从标准输入给出： $N$ $M$ $H_1$ $H_2$ $...$ $H_N$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_M$ $B_M$

输出格式

输出良好天文台的数量。

4 3
1 2 3 4
1 3
2 3
2 4

2

6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6

3

提示

$2 \leq N \leq 10^5$ $1 \leq M \leq 10^5$ $1 \leq H_i \leq 10^9$ $1 \leq A_i,B_i \leq N$ $A_i \neq B_i$ 多条道路可能连接同一对天文台。 输入中的所有数值均为整数。从 Obs. $1$，你可以通过一条道路到达 Obs. $3$。Obs. $1$ 的海拔不高于 Obs. $3$ 的海拔，因此 Obs. $1$ 不是良好天文台。

从 Obs. $2$，你可以通过一条道路到达 Obs. $3$ 和 $4$。Obs. $2$ 的海拔不高于 Obs. $3$ 的海拔，因此 Obs. $2$ 不是良好天文台。

从 Obs. $3$，你可以通过一条道路到达 Obs. $1$ 和 $2$。Obs. $3$ 的海拔高于 Obs. $1$ 和 $2$ 的海拔，因此 Obs. $3$ 是良好天文台。

从 Obs. $4$，你可以通过一条道路到达 Obs. $2$。Obs. $4$ 的海拔高于 Obs. $2$ 的海拔，因此 Obs. $4$ 是良好天文台。

因此，良好天文台是 Obs. $3$ 和 $4$，所以共有两个良好天文台。

标签: AtCoder|abc166C

来源

AtCoder|abc166C