AT_abc166_c [ABC166C] Peaks

题目描述

在 AtCoder 丘陵上有 $N$ 个观景台，第 $i$ 个观景台的海拔高度为 $H_i$。此外，有 $M$ 条道路，每条道路 $j$ 连接着观景台 $A_j$ 和观景台 $B_j$，且连接的观景台两两不同。

如果观景台 $i$ 的高度比通过一条道路可以到达的所有其他观景台的高度都高，则称观景台 $i$ 是一个“好观景台”。如果观景台 $i$ 没有通过一条道路可以到达的其他观景台，也认为它是好观景台。

请你求出好观景台的数量。

输入格式

输入以如下格式从标准输入给出。

$N$ $M$
$H_1$ $H_2$ $\ldots$ $H_N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

输出格式

输出好观景台的数量。

输入输出样例 #1

输入 #1

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

输出 #1

2

输入输出样例 #2

输入 #2

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

输出 #2

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$
• 可能存在多条道路连接同一对观景台。
• 输入中的所有数值均为整数。

样例解释 1

• 从观景台 $1$ 通过一条道路可以到达的观景台是观景台 $3$，但观景台 $1$ 的高度不高于观景台 $3$，所以观景台 $1$ 不是好观景台。
• 从观景台 $2$ 通过一条道路可以到达的观景台是观景台 $3$ 和观景台 $4$，但观景台 $2$ 的高度不高于观景台 $3$，所以观景台 $2$ 不是好观景台。
• 从观景台 $3$ 通过一条道路可以到达的观景台是观景台 $1$ 和观景台 $2$，观景台 $3$ 的高度都高于观景台 $1$ 和观景台 $2$，所以观景台 $3$ 是好观景台。
• 从观景台 $4$ 通过一条道路可以到达的观景台是观景台 $2$，观景台 $4$ 的高度高于观景台 $2$，所以观景台 $4$ 是好观景台。

因此，好观景台的数量为 $2$。

由 ChatGPT 4.1 翻译