Description

有n个点,m条无向边,给定这n个点的权值和这m条边连结的点.

求有多少个点比它只经过一条边就能到达的所有点各自的权值都更大.

Format

Input

第一行给出N，M 第二行给出N个点的权值 接下来M行，每行两个数字，代表边的情况

N，M<=1e5

Output

如题

Samples

输入数据 1

4 31 2 3 41 32 32 4

Copy

输出数据 1

2

思路:

用邻接表存树,存好后枚举所有点，找出它所有子节点，并判断它是否比它所有子节点各自的权值都更大,是则ans++,最后输出ans即可。

#include <bits/stdc++.h>using namespace std;int n,m,idx,t,x,y,h[1000001],vtx[1000001],nex[1000001],a[1000001],ans;void f(int a,int b){idx++;vtx[idx] = b;nex[idx] = h[a];h[a] = idx;}int main(){scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++) scanf("%d",&a[i]);memset(h,-1,sizeof(h));for(int i = 1; i <= m; i++){scanf("%d%d",&x,&y);f(x,y);f(y,x);}for(int i = 1; i <= n; i++){int fl = 0,p = h[i];while(p != -1){if(a[i] <= a[vtx[p]]){fl = 1;break;}p = nex[p];}if(fl == 0) ans++;}printf("%d",ans);return 0;}/*4 40 0 11 0 20 3 11 2 3*/

如果觉得《#Z0060. Peaks》对你有帮助，请点赞、收藏，并留下你的观点哦！