#6 麻布動物園

難易度

(13:05 更新) 概要を更新しました。水路を結ぶ2エリアについて、高さが同じ場合、水は双方向に流れます。 ## 概要 麻布動物園は、 $N$ 箇所のエリアに分かれています。 動物園にいるフレンズのために、全エリアに水を流すために、水路を $M$ 本作りました。水路 $i\ (1 \leq i \leq M)$ はエリア $a_i$ と $b_i$ を結んでいます。 しかし水路が完成してから、動物園の各エリアの標高が $h_i$ であり、水路を結ぶ $2$ 点の高さが違う場合、水は高いところから低いところにしか伝わらないという重大な欠陥があった事が分かりました。高さが同じ場合は水は双方向に流れます。 そこで動物園の園長であるあなたは、水源を設置するエリアをできるだけ少なくしながら、水路をつたって全エリアに水が流れるようにしたいです。 幾つのエリアに水源を設置すれば全エリアに水が流れるようになるか、求めてください。 ## 制約 - $2 \leq N \leq 10^5$ - $1 \leq M \leq min(\frac{N\times (N-1)}{2}, 10^5)$ - $1 \leq h_i \leq 10^9 \ (1 \leq i \leq N)$ - $1 \leq a_i < b_i \leq N \ (1 \leq i \leq M)$ - $(a_i,b_i)$ と $(a_j,b_j)$ は一致しない $(1 \leq i < j \leq M)$ ## 入力 $N$ $h_1$ $h_2$ ... $h_N$ $M$ $a_1$ $b_1$ ... $a_M$ $b_M$ ## 出力 最低で幾つのエリアに水源を設置すればいいかを出力してください。 ## 入出力例 ### 入出力例1 #### 入力 ``` 3 1 2 3 2 1 2 2 3 ``` #### 出力 ``` 1 ``` - エリア $3$ に水源を設置する事で全エリアに水が流れます。 ### 入出力例2 #### 入力 ``` 6 1 2 3 2 3 1 4 1 2 2 3 4 5 5 6 ``` #### 出力 ``` 2 ``` - 動物園の水路は何かの設計ミスで元からつながっていない事があります。 ### 入出力例3 #### 入力 ``` 7 5 3 5 4 2 1 4 7 1 2 2 3 2 5 2 6 4 5 5 6 6 7 ``` #### 出力 ``` 4 ```