Problem:


Score : 300 points

Problem Statement

There are N observatories in AtCoder Hill, called Obs. 1, Obs. 2, ..., Obs. N. The elevation of Obs. i is H_i.
There are also M roads, each connecting two different observatories. Road j connects Obs. A_j and Obs. B_j.

Obs. i is said to be good when its elevation is higher than those of all observatories that can be reached from Obs. i using just one road.
Note that Obs. i is also good when no observatory can be reached from Obs. i using just one road.

How many good observatories are there?

Constraints

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

Multiple roads may connect the same pair of observatories.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
H_1 H_2 ... H_N
A_1 B_1
A_2 B_2
:
A_M B_M

Output

Print the number of good observatories.

Sample Input 1

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

Sample Output 1

2

From Obs. 1, you can reach Obs. 3 using just one road. The elevation of Obs. 1 is not higher than that of Obs. 3, so Obs. 1 is not good.

From Obs. 2, you can reach Obs. 3 and 4 using just one road. The elevation of Obs. 2 is not higher than that of Obs. 3, so Obs. 2 is not good.

From Obs. 3, you can reach Obs. 1 and 2 using just one road. The elevation of Obs. 3 is higher than those of Obs. 1 and 2, so Obs. 3 is good.

From Obs. 4, you can reach Obs. 2 using just one road. The elevation of Obs. 4 is higher than that of Obs. 2, so Obs. 4 is good.

Thus, the good observatories are Obs. 3 and 4, so there are two good observatories.

Sample Input 2

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

Sample Output 2

3



Sample input:
4 3
1 2 3 4
1 3
2 3
2 4


Sample output:
2

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
arr = [0] + list(map(int, input().split()))
g = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

ans = 0
for i in range(1, n + 1):
    for j in g[i]:
        if arr[j] >= arr[i]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = [int(a) for a in input().split()]
X = [1] * N
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    if H[a] <= H[b]:
        X[a] = 0
    if H[b] <= H[a]:
        X[b] = 0
print(sum(X))

Submission status: Accepted

Solution code:
N, M =map(int, input().split())
H=list(map(int, input().split()))

A=[True]*N

for i in range(M):
	a, b = map(int, input().split())

	if H[a-1]>H[b-1]:
		A[b-1]=False
	elif H[a-1]==H[b-1]:
		A[a-1]=False
		A[b-1]=False
	elif H[a-1]<H[b-1]:
		A[a-1]=False

print(sum(A))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
H = list(map(int,input().split()))
L = [1]*n
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if H[a] == H[b]:
    L[a] = 0
    L[b] = 0
  elif H[a] < H[b]:
    L[a] = 0
  elif H[a] > H[b]:
    L[b] = 0
print(sum(L))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
H = list(map(int,input().split()))
L = [1]*n
for _ in range(m):
  a,b = map(int,input().split())
  if H[a-1] == H[b-1]:
    L[a-1] = 0
    L[b-1] = 0
  elif H[a-1] < H[b-1]:
    L[a-1] = 0
  elif H[a-1] > H[b-1]:
    L[b-1] = 0
print(sum(L))

Submission status: Accepted

Solution code:
n,m= map(int, input().split())
h = list(map(int, input().split()))
t = [0]*(n+1)
ans = 0
for i in range(m):
  a,b = map(int, input().split())
  if h[a-1]==h[b-1]:
    t[b]+=1
    t[a]+=1
  elif h[a-1]>h[b-1]:
    t[b]+=1
  elif h[a-1]<h[b-1]:
    t[a]+=1

for i in range(1,n+1):
  if t[i] == 0:
    ans +=1
print(ans)

Submission status: Accepted

Solution code:
import math , sys

N , M = list(map(int, input().split()))
H = list(map(int, input().split()))
Es = [[] for _ in range(N)]
for i in range(M):
    A , B = list(map(int, input().split()))
    A -=1 ; B-=1
    Es[A].append(B)
    Es[B].append(A)
ans = 0
for i in range(N):
    Es[i] = list(set(Es[i]))
for i in range(N):
    if len(Es[i]) == 0:
        ans+=1
    else:
        Max = max( [ H[Es[i][j]] for j in range( len(Es[i]) ) ] )
        if H[i] > Max:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
ans = [1]*n
for i in range(m):
    if h[ab[i][0]-1] == h[ab[i][1]-1]:
        ans[ab[i][0]-1] = 0
        ans[ab[i][1]-1] = 0
    elif h[ab[i][0]-1] > h[ab[i][1]-1]:
        ans[ab[i][1]-1] = 0
    else:
        ans[ab[i][0]-1] = 0
print(sum(ans))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int,input().split()))

tmp = [1]*N

for m in range(M):
    a, b = map(int, input().split())

    if H[a-1] > H[b-1]:
        tmp[b-1] = 0
    elif H[a-1] < H[b-1]:
        tmp[a-1] = 0
    else:
        tmp[a-1] = 0
        tmp[b-1] = 0

print(sum(tmp))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
A=[0]*M;B=[0]*M
C=[0]*N
for i in range(M):
  A[i],B[i]=map(int,input().split())

for i in range(M):
  if H[A[i]-1]<H[B[i]-1]:C[A[i]-1]+=1
  elif H[A[i]-1]>H[B[i]-1]:C[B[i]-1]+=1
  else:C[A[i]-1]+=1;C[B[i]-1]+=1
print(C.count(0))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
cnt=[1 for _ in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    A-=1
    B-=1
    if H[A]>H[B]:
        cnt[B]=0
    elif H[A]<H[B]:
        cnt[A]=0
    else:
        cnt[A]=0
        cnt[B]=0
print(cnt.count(1))

Submission status: Accepted

Solution code:
import bisect

class Peaks:
    def __init__(self, N, H, next_obs_heights):
        self.N = N
        self.H = H
        self.next_obs_heights = next_obs_heights

    def solve(self):
        result = 0

        for i in range(N):
            if len(next_obs_heights[i]) == 0:
                result += 1
                continue

            next_num = len(next_obs_heights[i])
            if self.H[i] > next_obs_heights[i][next_num-1]:
                result += 1

        print(result)

N, M = map(int, input().split())
H = list(map(int, input().split()))
next_obs_heights = [ [] for i in range(N) ]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    bisect.insort(next_obs_heights[a], H[b])
    bisect.insort(next_obs_heights[b], H[a])

peaks = Peaks(N, H, next_obs_heights)
peaks.solve()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
mx = [0 for i in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    mx[a] = max(mx[a], H[b])
    mx[b] = max(mx[b], H[a])
ans = 0
for i in range(N):
    if H[i] > mx[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


def LI(): return list(map(int,input().split()))


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))


# rstrip().decode('utf-8')
import numpy as np

def main():
	n,m=MI()
	H=LI()
	G=[[] for _ in range(n+1)]
	for _ in range(m):
		a,b=MI()
		G[a].append(H[b-1])
		G[b].append(H[a-1])
	#print(G)
	
	ans=0
	for i in range(1,n+1):
		if G[i]==[]:
			ans+=1
		elif H[i-1]>max(G[i]):
			ans+=1
	print(ans)
	









if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
h=list(map(int,input().split()))
g = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
ans=0
for j in range(n):
    for i in g[j]:
        if h[j]<=h[i]:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int, input().split()))
AB = [list(map(int,input().split()))for i in range(M)]
good = [True]*N
for i in range(M):
        a,b = AB[i]
        if H[a-1] > H[b-1]:
            good[b-1] = False
        elif H[a - 1] < H[b - 1]:
            good[a - 1] = False
        else:
            good[a - 1] = False
            good[b - 1] = False
#print(good)
print(good.count(True))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
g = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

ans = 0
for i in range(N):
    flg = True
    for j in g[i]:
        flg = flg & (H[i] > H[j])
    ans += flg
print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
list_h = list(map(int, input().split()))
table = [1] * N

for i in range(M):
  A, B = list(map(int, input().split()))
  if list_h[B-1] < list_h[A-1]:
    table[B-1] = 0
  elif list_h[A-1] < list_h[B-1]:
    table[A-1] = 0
  else:
    table[A-1] = 0
    table[B-1] = 0

print(str(sum(table)))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = [0] + list(map(int, input().split()))

g = [[] for _ in range(N+1)]
for i in range(M):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)

ans = 0
for j in range(1, N+1):
  for k in g[j]:
    if H[j] <= H[k]:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# nは展望台の数　mは道の数
n,m = map(int,input().split())
high = list(map(int,input().split()))

a = []

for x in range(m):
    b = list(map(int,input().split()))
    a.append(b)


loser = []

for y in a:
    high1 = high[y[0]-1]
    high2 = high[y[1]-1]
    if high1 > high2:
        loser.append(y[1])
    elif high1 ==  high2:
        loser.append(y[0])
        loser.append(y[1])
    else:
        loser.append(y[0])

new_loser = list(set(loser))
print(n-len(new_loser))

Submission status: Accepted

Solution code:

n, m = map(int, input().split())
l = list(map(int, input().split()))
cor = [[] for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    cor[a].append(b)
    cor[b].append(a)

ans = 0
for i in range(n):
    max_h = l[i]
    cnt = 1
    co = list(set(cor[i]))
    for j in range(len(co)):
        if l[co[j]] >= max_h:
            cnt = 0
            break
    ans += cnt

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

N, M = list(map(int, input().split()))
h_list = list(map(int, input().split()))
h_dict = {i + 1: h for i, h in enumerate(h_list)}
h_set = set(h_dict.keys())
no_list = []

for _ in range(M):
    a, b = list(map(int, input().split()))
    if h_dict[a] == h_dict[b]:
        no_list.append(a)
        no_list.append(b)
    elif h_dict[a] > h_dict[b]:
        no_list.append(b)
    else:
        no_list.append(a)

no_set = set(no_list)
ans = len(h_set - no_set)

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
height = [0] + list(map(int, input().split()))
mawari = [0] * (n+1) 
ans = 0

for _ in range(m):
    a, b = map(int, input().split())
    mawari[a] = max(mawari[a], height[b])
    mawari[b] = max(mawari[b], height[a])
    

for i in range(1,n+1):
    if height[i]> mawari[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
[N, M] = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]
dic = {}
for i in range(M):
    [a, b] = [int(i) for i in input().split()]
    if a in dic:
        dic[a].append(b)
    else:
        dic[a] = [b]
    if b in dic:
        dic[b].append(a)
    else:
        dic[b] = [a]

ans = 0
for i in range(1, N+1):
    s = H[i-1]
    t = 0
    if i in dic:
        for j in range(len(dic[i])):
            if s <= H[dic[i][j]-1]:
                t += 1
                break
        if t == 0:
            ans += 1
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
h = list(map(int, input().split()))
ab = [map(int, input().split()) for _ in range(m)]
a,b = [list(i) for i in zip(*ab)]
Max = []
for i in range(n):
    Max.append(0)
# print(Max)
ans = 0
for i in range(m):
    Max[a[i]-1] = max(Max[a[i]-1],h[b[i]-1])
    Max[b[i]-1] = max(Max[b[i]-1],h[a[i]-1])

for i in range(n):
    if h[i] > Max[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h = list(map(int,input().split()))
l = list({i} for i in range(n+1))
for i in range(m):
    a,b = map(int,input().split())
    l[a].add(b)
    l[b].add(a)
    
for i in range(len(l)):
    l[i] = list(l[i])
good = set()
for i in range(1,len(l)):
    l[i].remove(i)
    for j in range(len(l[i])):
        if h[l[i][j]-1] >= h[i-1]:
            break
    else:
        good.add(i)
print(len(good))

Submission status: Accepted

Solution code:
n,m = list(map(int, input().split()))
h = list(map(int, input().split()))
hoge = [[] for _ in range(n)]
for i in range(m):
  a,b = list(map(int, input().split()))
  hoge[a - 1].append(b - 1)
  hoge[b - 1].append(a - 1)
  
cnt = 0
for i in range(n):
  if hoge[i]:
    flag = True
    for j in hoge[i]:
      if h[i] <= h[j]:
        flag = False
    if flag:
      cnt += 1
  else:
    cnt += 1
        
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for i in range(M)]
answer = [1]*N

for i in range(M):
	if H[AB[i][0]-1] > H[AB[i][1]-1]:
		answer[AB[i][1]-1] = 0
	elif H[AB[i][0]-1] == H[AB[i][1]-1]:
		answer[AB[i][1]-1] = 0
		answer[AB[i][0]-1] = 0
	else:
		answer[AB[i][0]-1] = 0

print(sum(answer))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    H = [None]
    H.extend(list(map(int, input().split())))
    bad = set([])
    for _ in range(M):
        A, B = map(int, input().split())
        if H[A] > H[B]:
            bad.add(B)
        elif H[A] < H[B]:
            bad.add(A)
        else:
            bad.add(A)
            bad.add(B)
    print(N - len(bad))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
lst = list(map(int,input().split()))
lst2 = []
for i in range(n):
    lst3 = [lst[i]]
    lst2.append(lst3)

for i in range(m):
    a, b = map(int,input().split())
    a = a - 1
    b = b - 1
    lst2[a].append(lst2[b][0])
    lst2[b].append(lst2[a][0])

ans = 0
for i in range(n):
    x = lst2[i][0]
    lst2[i].sort()
    lst2[i].reverse()
    if (len(lst2[i]) == 1):
        ans = ans + 1
    elif (x == lst2[i][0]):
        lst2[i].pop(0)
        y = lst2[i][0]
        if (x != y):
            ans = ans + 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
Hlist = list(map(int,input().split()))

anslist = [1]*N
for i in range(M):
  A,B = map(int,input().split())
  #print (Hlist[A-1])
  #print (Hlist[B-1])
  if Hlist[A-1]<Hlist[B-1]:
    anslist[A-1]=0
  elif Hlist[A-1]>Hlist[B-1]:
    anslist[B-1]=0
  elif Hlist[A-1]==Hlist[B-1]:
    anslist[A-1]=0
    anslist[B-1]=0
    
#print (anslist)
print (sum(anslist))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))

# N,M=O(10^5)なので、O(N+M)で解く
# 各ノードについて、隣接する展望台の高さの最大値を更新する
neighbor_max = [0] * N
for _ in range(M):
  A, B = map(int, input().split())
  neighbor_max[A - 1] = max(neighbor_max[A - 1], H[B - 1])
  neighbor_max[B - 1] = max(neighbor_max[B - 1], H[A - 1])

# 各ノードについて、自身の高さと、隣接する展望台の高さの最大値を比較する
# 接続を一つも持たないノードについても、計算は正しい
ans = 0
for i in range(N):
  if H[i] > neighbor_max[i]: ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
H = list(map(int, input().split()))

edges = defaultdict(list)

for _ in range(M):
    a, b = map(lambda x:int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)

ans = 0
for i in range(N):
    ok = True
    for adj in edges[i]:
        if H[adj] >= H[i]:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
l=[1]*n
for i in range(m):
  a,b=map(int,input().split())
  if h[a-1]==h[b-1]:
    l[a-1]=0
    l[b-1]=0
  if h[a-1]>h[b-1]:
    l[b-1]=0
  if  h[a-1]<h[b-1]:
    l[a-1]=0
print(l.count(1))

Submission status: Accepted

Solution code:
# C - Peaks

n,m = map(int, input().split())
h = list(map(int,input().split()))
ab = []
for i in range(m):
    ab.append(list(map(int,input().split())))

peak = [1]*n
for i in range(m):
    if h[ab[i][0]-1] >= h[ab[i][1]-1]:
        peak[ab[i][1]-1] = 0
    if h[ab[i][0]-1] <= h[ab[i][1]-1]:
        peak[ab[i][0]-1] = 0
print(sum(peak))

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
H = list(map(int,input().split()))
AB = []
ans = 0
for i in range(m):
    AB.append(list(map(int,input().split())))
    AB[-1][0] -= 1
    AB[-1][1] -= 1
ok = [1]*n
for i in range(m):
    if H[AB[i][0]] >= H[AB[i][1]]:
        ok[AB[i][1]] = 0
    if H[AB[i][0]] <= H[AB[i][1]]:
        ok[AB[i][0]] = 0
for i in ok:
    if i:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
A = [True for i in range(N)]
for i in range(M) :
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    if(H[a] <= H[b]) :
        A[a] = False
    if(H[b] <= H[a]) :
        A[b] = False

ans = 0
for i in range(N) :
    if(A[i]) :
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
D = dict()
for i in range(1, n+1):
    D[i] = h[i-1]
L = [1 for i in range(n)]
for _ in range(m):
    a, b =map(int, input().split())
    if D[a] > D[b]:
        L[b-1] = 0
    elif D[a] == D[b]:
        L[a-1] = 0
        L[b-1] = 0
    else:
        L[a-1] = 0
ans = 0
for e in L:
    ans += e
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
ways = [list(map(int, input().split())) for i in range(M)]
observatoryList = [1] * N
for i in range(M):
  if H[ways[i][0] - 1] <= H[ways[i][1] - 1]:
    observatoryList[ways[i][0] - 1] = 0
  if H[ways[i][0] - 1] >= H[ways[i][1] - 1]:
    observatoryList[ways[i][1] - 1] = 0
goodObservatoryCount = observatoryList.count(1)
print(goodObservatoryCount)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
peaks = [1] * N
for i in range(M):
    A, B = map(int, input().split())
    if H[A - 1] > H[B - 1]:
        peaks[B - 1] = 0
    elif H[B - 1] > H[A - 1]:
        peaks[A - 1] = 0
    else:
        peaks[A - 1] = 0
        peaks[B - 1] = 0

print(sum(peaks))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
array = list(map(int,input().split()))
ans = [1]*N
for i in range (M):
  A,B = map(int,input().split())
  if array[A - 1] < array[B - 1]:
    ans[A - 1] = 0
  elif array[A - 1] > array[B - 1]:
    ans[B - 1] = 0
  else:
    ans[A-1],ans[B-1] = 0,0
print( sum(ans) )

Submission status: Accepted

Solution code:
def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))
def inNL(n):
    return [list(map(int,input().split())) for i in range(n)]

n,m = inL()
h = inL()
ab = inNL(m)

l = [1]*n
for a,b in ab:
    if h[a-1]>h[b-1]:
        l[b-1] = 0
    elif h[a-1]==h[b-1]:
        l[a-1]=l[b-1]=0
    else:
        l[a-1] = 0
#print(l)
print(l.count(1))

Submission status: Accepted

Solution code:
n,m = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
a,b = [],[]
for i in range(m):
  a1,b1 = [int(x) for x in input().split()]
  a.append(a1-1)
  b.append(b1-1)
ans = [1] * n
for i in range(m):
  if h[a[i]] < h[b[i]]:
    ans[a[i]] = 0
  elif h[a[i]] > h[b[i]]:
    ans[b[i]] = 0
  else:
    ans[a[i]] = 0
    ans[b[i]] = 0
c = 0
for i in range(n):
  if ans[i] == 1:
    c += 1
#print(ans)
print(c)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
h = list(map(int, input().split()))
neighbor = [[] for _ in range(n)]

for i in range(m):
    a, b = list(map(int, input().split()))
    neighbor[a - 1].append(b - 1)
    neighbor[b - 1].append(a - 1)

cnt = 0
for i in range(n):
    if all([h[i] > h[j] for j in neighbor[i]]):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:

def main():
    n, m = map(int, input().split(" "))
    ls=[{} for _ in range(n)]
    h = list(map(int, input().split(" ")))
    for i in range(n):
        ls[i] = [h[i]]
    ab = []
    for i in range(m):
        ab.append(list(map(lambda i:int(i)-1, input().split(" "))))
    for i in range(m):
        if ls[ab[i][0]][0] >= ls[ab[i][1]][0]:
            ls[ab[i][1]].append(ls[ab[i][0]][0]+1)
        if ls[ab[i][1]][0] >= ls[ab[i][0]][0]:
            ls[ab[i][0]].append(ls[ab[i][1]][0] + 1)
    cnt = 0
    for i in range(n):
        if ls[i][0] == max(ls[i]):
            cnt += 1
    print(cnt)

        

    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
heights = [0] + list(map(int, input().split()))
routes = [[] for _ in range(N+1)]
for __ in range(M):
  a, b = map(int, input().split())
  routes[a].append(b)
  routes[b].append(a)
answer = 0
for i, route in enumerate(routes):
  if i == 0:
    continue
  if len(route) == 0:
    answer += 1
    continue
  else:
    highest = True
    for dist in route:
      if heights[i] <= heights[dist]:
        highest = False
        break
    if highest:
      answer += 1
print(answer)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h = list(map(int,input().split()))

g = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)

cnt = n
for i in range(n):
  for j in g[i]:
    if h[i] <= h[j]:
      cnt -= 1
      break
print(cnt)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
Hlist=list(map(int,input().split()))
ABlist=[]
for _ in range(M):
    ABlist.append(list(map(int,input().split())))
flaglist=[1]*N
for row in ABlist:
    one=row[0]-1 #indexと番号の調整
    two=row[1]-1
    if Hlist[one]<=Hlist[two]:
        flaglist[one]=0
    if Hlist[one]>=Hlist[two]:
        flaglist[two]=0
print(sum(flaglist))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
OK = [True] * N
for _ in range(M):
    A, B = map(lambda x: int(x)-1, input().split())
    if H[A] < H[B]:
        OK[A] = False
    elif H[A] > H[B]:
        OK[B] = False
    else:
        OK[A] = False
        OK[B] = False

ans = sum(OK)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

def getval():
    n,m = map(int,input().split())
    h = list(map(int,stdin.readline().split()))
    p = [list(map(int,stdin.readline().split())) for i in [0]*m]
    return n,m,h,p

def main(n,m,h,p):
    g = [[] for i in range(n)]
    for i in p:
        g[i[0]-1].append(i[1]-1)
        g[i[1]-1].append(i[0]-1)
    ans = 0
    for i in range(n):
        if not g[i]:
            ans += 1
        else:
            temp = h[i]
            flag = True
            for j in g[i]:
                if h[j]>=temp:
                    flag = False
                    break
            if flag:
                ans += 1
    print(ans)
                

if __name__=="__main__":
    n,m,h,p = getval()
    main(n,m,h,p)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())                       
h =list(map(int,input().split()))
cnt = 0
l = [[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split()) 
    l[a-1].append(h[b-1])
    l[b-1].append(h[a-1])

for i in range(n):
    if l[i] == []:
        cnt+=1

    elif h[i] > max(l[i]):
        cnt +=1
    

print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
c = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    c[a].append(b)
    c[b].append(a)

ans = 0
for i in range(n):
    high = h[i]
    for j in c[i]:
        if h[j] >= high:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import chain


def solve(
    N: int, M: int, H: "List[int]", A: "List[int]", B: "List[int]"
):
    ok = [1 for _ in range(N)]
    for a, b in zip(A, B):
        if H[a - 1] <= H[b - 1]:
            ok[a - 1] = 0
        if H[b - 1] <= H[a - 1]:
            ok[b - 1] = 0

    return sum(ok)


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    H = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    answer = solve(N, M, H, A, B)
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
ri = lambda: map(int, input().split())

N, M = ri()
H = list(ri())
T = [0]*N
for _ in range(M):
    a, b = ri()
    T[a-1] = max(T[a-1], H[b-1])
    T[b-1] = max(T[b-1], H[a-1])

print(sum(1 for i, h in enumerate(T) if h == 0 or h < H[i]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
A=[[] for i in range(n)]
for i in range(m) :
    a,b=map(int,input().split())
    A[a-1].append(h[b-1])
    A[b-1].append(h[a-1])

count=0
for i in range(n) :
    if A[i]==[] :
        count+=1
    elif max(A[i])<h[i] :
        count+=1
    else :
        continue

print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))

graph = [[] for _ in range(N)]

for query in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

ans = 0

for now in range(N):
    good = True
    for neighbor in graph[now]:
        if H[now] <= H[neighbor]:
            good = False
    if good:
        ans += 1
        #print(now)

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())

H=list(map(int,input().split()))

graph=[[0] for _ in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    graph[A-1].append(H[B-1])
    graph[B-1].append(H[A-1])

ans=0

for i in range(N):
    if H[i]>max(graph[i]):
        ans+=1
        
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
yoi = [1] * N

for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    if H[A] > H[B]:
        yoi[B] = 0
    elif H[B] > H[A]:
        yoi[A] = 0
    else:
        yoi[A] = 0
        yoi[B] = 0

print(sum(yoi))

Submission status: Accepted

Solution code:
N,M = map(int, input().split())

H=list(map(int,input().split()))

graph=[[0] for _ in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    graph[A-1].append(H[B-1])
    graph[B-1].append(H[A-1])

ans=0

for i in range(N):
    if H[i]>max(graph[i]):
        ans+=1
        
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
glaph = [[] for _ in range(N)]

for i in range(M):
  A,B = map(int,input().split())
  A -= 1
  B -= 1
  glaph[A].append(B)
  glaph[B].append(A)
  
ans = 0
for j in range(N):
  check = True
  for k in glaph[j]:
    if H[j] <= H[k]:
      check = False
      break
  if check:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    n , m = map( int , input().split() )
    h = list( map( int , input().split() ) )
    goods = [ 1 for i in range(n) ]
    for i in range( m ):
        a , b = map( lambda x : int(x) - 1  , input().split() )
        if ( h[a] > h[b] ):
            goods[ b ] = 0
        if ( h[a] < h[b] ):
            goods[ a ] = 0
        if ( h[a] == h[b] ):
            goods[ a ] = 0
            goods[ b ] = 0
    print( sum(goods) )
main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
way=[[] for i in range(n)]
H = list(map(int,input().split()))
for i in range(m):
    a,b=map(int,input().split())
    way[a-1].append(b-1)
    way[b-1].append(a-1)
ans=0
for i in range(n):
    high=True
    for j in way[i]:
        if H[i]<=H[j]:
            high=0
            break
    if high:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
h = list(map(int,input().split()))
l = [1]*n
for i in range(m):
  a, b = map(int,input().split())
  if h[a-1] == h[b-1]:
    l[a-1] = 0
    l[b-1] = 0
  if h[a-1] > h[b-1]:
    l[b-1] = 0
  if h[a-1] < h[b-1]:
    l[a-1] = 0
print(l.count(1))

Submission status: Accepted

Solution code:
n, m = [int(i) for  i in input().split()]
h = [int(i) for i in input().split()]
edges = [[] for i in range(n)]
for _ in range(m):
  edge = [int(i)-1 for i in input().split()]
  edges[edge[0]].append(edge[1])
  edges[edge[1]].append(edge[0])
cnt = 0

for i in range(n):
  flg = True
  for j in edges[i]:
    if h[i] <= h[j]:
      flg = False
      break
  if flg:
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
way=[[] for i in range(n)]
H = list(map(int,input().split()))
for i in range(m):
    a,b=map(int,input().split())
    way[a-1].append(b-1)
    way[b-1].append(a-1)

for i in range(n):
    way[i]=list(set(way[i]))

ans=0
for i in range(n):
    high=True
    for j in way[i]:
        if H[i]<=H[j]:
            high=0
            break
    if high:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    A = [0] * M
    B = [0] * M
    for i in range(M):
        A[i], B[i] = map(int, input().split())

    l = [1] * N
    for i in range(M):
        if H[A[i] - 1] < H[B[i] - 1]:
            l[A[i] - 1] -= 1
        elif H[A[i] - 1] > H[B[i] - 1]:
            l[B[i] - 1] -= 1
        else:
            l[A[i] - 1] -= 1
            l[B[i] - 1] -= 1
    print(l.count(1))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
H = list(map(int,input().split()))
A, B = [], []
for _ in range(M):
  a, b = map(int,input().split())
  A.append(a)
  B.append(b)

L = [1] * N

for i in range(M):
  ai = A[i] - 1
  bi = B[i] - 1
  if H[ai] > H[bi]:
    L[bi] = 0
  elif H[bi] > H[ai]:
    L[ai] = 0
  else:
    L[ai], L[bi] = 0, 0

print(L.count(1))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = [int(x) for x in input().split()]

d = [1] * N

for i in range(M):
    A, B = map(int, input().split())
    if H[A - 1] >= H[B - 1]:
        d[B - 1] = 0
    if H[A - 1] <= H[B - 1]:
        d[A - 1] = 0


print(sum(d))