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:
# class UnionFind():
#     def __init__(self, n):
#         self.n = n
#         self.parents = [-1] * n

#     def find(self, x):
#         if self.parents[x] < 0:
#             return x
#         else:
#             self.parents[x] = self.find(self.parents[x])
#             return self.parents[x]

#     def union(self, x, y):
#         x = self.find(x)
#         y = self.find(y)

#         if x == y:
#             return

#         if self.parents[x] > self.parents[y]:
#             x, y = y, x

#         self.parents[x] += self.parents[y]
#         self.parents[y] = x

#     def size(self, x):
#         return -self.parents[self.find(x)]

#     def same(self, x, y):
#         return self.find(x) == self.find(y)

#     def members(self, x):
#         root = self.find(x)
#         return [i for i in range(self.n) if self.find(i) == root]

#     def roots(self):
#         return [i for i, x in enumerate(self.parents) if x < 0]

#     def group_count(self):
#         return len(self.roots())

#     def all_group_members(self):
#         return {r: self.members(r) for r in self.roots()}

#     def __str__(self):
#         return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M = map(int, input().split())
H = list(map(int, input().split()))
AB = []
# uf = UnionFind(N)
dic = {}
ansl = []

for i in range(M):
    ab = list(map(int, input().split()))
    # ab[0] -= 1
    # ab[1] -= 1
    # uf.union(*ab)
    AB.extend(ab)
    # ansl.append(max([H[ab[0]-1],H[ab[0]-1]]))
    dic.setdefault(ab[0],[]).append(ab[1])
    dic.setdefault(ab[1],[]).append(ab[0])

# print(dic)
# print(uf.all_group_members())
# ans = len(set(ansl))
ans = N-len(set(AB))
for k,v in dic.items():
    if H[k-1] > max(list(map(lambda x: H[x-1], v))):
        ans += 1

print(ans)

Submission status: Accepted

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

    graph = [[] for _1 in range(N)]
    for a,b in AB:
        graph[a-1].append(b)
        graph[b-1].append(a)
    ans = 0
    #print(graph)

    for i in range(N):
        height = H[i]
        for j in graph[i]:
            if height <= H[j-1]:
                #print(height,H[j-1])
                break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
A=[0]*M
B=[0]*M
S=[]
for i in range(M):
	A[i],B[i]=map(int,input().split())
	if H[A[i]-1]<H[B[i]-1]:
		S.append(A[i])
	elif H[A[i]-1]>H[B[i]-1]:
		S.append(B[i])
	else:
		S.append(A[i])
		S.append(B[i])
As=set(S)
count=len(As)
print(N-count)

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
H=list(map(int,input().split()))
h=[]
for m in range(M):
    a,b=list(map(int,input().split()))
    if a-1<=N and b-1<=N:
        if H[a-1]<=H[b-1]:
            h.append(a-1)
        if H[a-1]>=H[b-1]:
            h.append(b-1)
h2=set(h)
ans=N-len(h2)
print(ans)

Submission status: Accepted

Solution code:
def init_road(M, road):
    for _ in range(M):
        a, b = [int(i) for i in input().split()]
        road.setdefault(a,set())
        road.setdefault(b,set())
        road[a].add(b)
        road[b].add(a)
    return road       

def good_peak_cnt(key, values):
    key = key - 1
    key_height = peaks[key]
    if len(values) == 0:
        pass
    else :
        for v in values:
            v = v -1
            v_height = peaks[v]
            if v_height >= key_height:
                return False
    return True

road = dict()
peaks = dict()

N, M = [int(i) for i in input().split()]
heights = [int(i) for i in input().split()]

for i, h in enumerate(heights):
    peaks.setdefault(i, h)

road = init_road(M,road)

cnt = 0
peaks_with_road = set()
for key, values in road.items():
    for r in values:
        peaks_with_road.add(r)
    if good_peak_cnt(key, values):
        cnt += 1

peaks_with_no_road = N - len(peaks_with_road)
output = cnt + peaks_with_no_road
print(output)

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))
import numpy as np
C=np.ones(N)
d=0
def m(a,b):
  if H[b-1]>H[a-1]:
    return [a,a]
  if H[a-1]>H[b-1]:
    return [b,b]
  if H[b-1]==H[a-1]:
    return [a,b]
for i in range(M):
  C[m(A[i],B[i])[0]-1]=0
  C[m(A[i],B[i])[1]-1]=0
for j in range(N):
  d=d+C[j]
print(int(d))

Submission status: Accepted

Solution code:
def main():

  N, M = map(int, input().split())

  hyoko = list(map(int, input().split()))
  path =[]
  for i in range(M):
    A, B = map(int, input().split())
    path .append([A,B])
  
  # print('N:{},M:{}'.format(N,M))
  # print('hyoko:{}'.format(hyoko))
  # print('path:{}'.format(path))

  good_obs = [1 for i in range(N)]

  for i in path:
    A = i[0]-1
    B = i[1]-1
    # print('path:{},A{}:{},B{}:{}'.format(i,A,hyoko[A],B,hyoko[B]))
    if hyoko[A] > hyoko[B]:
      good_obs[B] = 0
    elif hyoko[B] > hyoko[A]:
      good_obs[A] = 0
    else:
      good_obs[A] = 0
      good_obs[B] = 0
    

  print(sum(good_obs))


if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import numpy as np

n, m = map(int, input().split())

h = {}
for k, v in zip(range(1,n+1),[k for k in map(int, input().split())]):
    h[k] = v 

miti = []
for i in range(m):
    temp = [k for k in map(int, input().split())]
    miti.append(temp)

x = np.zeros(n)

for i in range(m):
    if h[miti[i][0]] < h[miti[i][1]]:
        x[miti[i][0]-1] =+1
    elif h[miti[i][0]] > h[miti[i][1]]:
        x[miti[i][1]-1] =+1
    elif h[miti[i][0]] == h[miti[i][1]]:
        x[miti[i][0]-1] =+1
        x[miti[i][1]-1] =+1

print(sum(x == 0))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = [int(x) for x in input().split()]

ans = [1 for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    if h[a-1] >= h[b-1]:
        ans[b-1] = 0
    if h[b-1] >= h[a-1]:
        ans[a-1] = 0

count = ans.count(1)
print(count)

Submission status: Accepted

Solution code:

N, M = map(int, input().split())

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

S = [list(map(int, input().split())) for i in range(M)]

d=set(list(range(N)))

v=[]

for i in range(M):
    if H[S[i][0]-1]<H[S[i][1]-1]:
        v.append(S[i][0]-1)
    elif H[S[i][0]-1]>H[S[i][1]-1]:
        v.append(S[i][1]-1)
    elif H[S[i][0]-1]==H[S[i][1]-1]:
        v.append(S[i][0]-1)
        v.append(S[i][1] - 1)

u=set(v)

d=d-u

print(len(d))

Submission status: Accepted

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

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

ls = [1 for _ in range(N)]

for m in range(M):
    A, B = map(int, input().split())

    if ls[A - 1]: 
        ls[A - 1] = 0
        if H[A - 1] > H[B - 1]:
            ls[A - 1] = 1

    if ls[B - 1]: 
        ls[B - 1] = 0
        if H[B - 1] > H[A - 1]:
            ls[B - 1] = 1


print(sum(ls))

Submission status: Accepted

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

ANS=[1]*N
path=[]

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

print(sum(ANS))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import os

def main():
	n,m = map(int, input().split())
	h_list = list(map(int, input().split()))
	ans = [1]*n
	for i in range(m):
		a,b = map(int, input().split())
		if h_list[a-1] < h_list[b-1]:
			ans[a-1] = 0	
		elif h_list[a-1] == h_list[b-1]:
			ans[a-1] = 0
			ans[b-1] = 0
		else:
			ans[b-1] = 0
	print(sum(ans))			

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import copy
n,m=map(int,input().split())
h=[0]+list(map(int,input().split()))
hh=copy.copy(h)
for i in range(m):
  a,b=map(int,input().split())
  if hh[a]>hh[b]:
    h[b]=h[a]
  elif hh[a]<hh[b]:
    h[a]=h[b]
  else:
    h[a]+=1
    h[b]+=1
cnt=0
for j in range(1,n+1):
  if h[j]==hh[j]:
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
Hnew=H
Hdel=list()
Hdel2=list()
AB=list()
for i in range(M):
    AB.append(list(map(int, input().split())))
    

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

        
Hdel2=list(set(Hdel2))        
Hdel=list(set(Hdel))
print(len(H)-len(Hdel2))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h = list(map(int,input().split()))
a = []
b = []
cnt = 0
while True:
  try:
    ta,tb = map(int,input().split())
    a.append(ta)
    b.append(tb)
  except:
    break
    
H = [0]*n

for i in range(m):

  if h[a[i]-1]>h[b[i]-1]:
    H[b[i]-1]-=1
  
  if h[a[i]-1]==h[b[i]-1]:
    H[a[i]-1]-=1
    H[b[i]-1]-=1
  if h[a[i]-1]<h[b[i]-1]:
    H[a[i]-1]-=1
n = [1 for i in H if i>=0]
print(len(n))

Submission status: Accepted

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

def add_list(key, value, d):
    if key not in d:
        d[key] = []
    d[key].append(value)
    return d

for i in range(M):
    a, b = input().split()
    path = add_list(a, H[int(b)-1], path)
    path = add_list(b, H[int(a)-1], path)

count = 0
for j in range(N):
    if str(j+1) not in path.keys():
        count += 1
        continue
    if H[j] > max(path[str(j+1)]):
        count += 1
print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
load = [ [H[i]] for i in range(N)]
ans = 0

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

for i in range(N):
    if max(load[i]) == load[i][0]:
        ans += 1
        if len(load[i]) != 1:
            for j in range(len(load[i])-1):
                if load[i][0] == load[i][j+1]:
                    ans -= 1
                    break
    

#print(load)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
highest = [True for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    if H[a] == H[b]:
        highest[a] = False
        highest[b] = False
    elif H[a] > H[b]:
        highest[b] = False
    else:
        highest[a] = False
print(len([h for h in highest if h]))

Submission status: Accepted

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

Submission status: Accepted

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

n_list =[x for x in range(1,n+1)]
ze = dict(zip(n_list, [0 for i in range(len(n_list))]))

for i in ab:
    if (h[i[0]-1]  > h[i[1]-1]):
        ze[i[1]] += 1
    elif (h[i[0]-1]  < h[i[1]-1]) :
        ze[i[0]] += 1
    elif h[i[0]-1]  == h[i[1]-1]:
        ze[i[0]] += 1
        ze[i[1]] += 1

res = 0
for k, v in ze.items():
    if v == 0:
        res += 1
print(res)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = [1] * (n + 1)
l[0] = 0 
h = list(map(int, input().strip().split()))
h.insert(0, 0)
 
for i in range(m):
  a, b = map(int, input().split())
  if h[a] == h[b] :
    l[a] = l[b] = 0
  elif h[a] < h[b]:
    l[a] = 0
  else :
    l[b] = 0
  
 
print(sum(l))

Submission status: Accepted

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

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

cnt = 0
for i in range(n):
  graph[i].sort(reverse=True)
  if graph[i]:
    if graph[i][0][0] < H[i]:  
      cnt += 1
  else:
    cnt += 1
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

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

ans_lst = ["N"]*n

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

    if ha > hb:
        if ans_lst[a-1] != "F":
            ans_lst[a-1] = "T"
        ans_lst[b-1] = "F"
    elif ha < hb:
        if ans_lst[b-1] != "F":
            ans_lst[b-1] = "T"
        ans_lst[a-1] = "F"
    elif ha == hb:
        ans_lst[a-1] = "F"
        ans_lst[b-1] = "F"
        
cnt = 0
for moji in ans_lst:
    if moji == "N" or moji == "T":
        cnt += 1
print(cnt)

Submission status: Accepted

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

check_h = [1] * N

for i in range(len(road)):
    a, b = road[i]
    if H[a] <= H[b]:
        check_h[a] = 0
    if H[b] <= H[a]:
        check_h[b] = 0
print(sum(check_h))

Submission status: Accepted

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

a_b.sort()
a = [0] * (1+n)
check = 0
for i in range(m):
    if i == 0:
        if h[int(a_b[i][0])-1] > h[int(a_b[i][1])-1]:
            a[int(a_b[i][1])] = -1
        elif h[int(a_b[i][0])-1] < h[int(a_b[i][1])-1]:
            a[int(a_b[i][0])] = -1
        elif h[int(a_b[i][0])-1] == h[int(a_b[i][1])-1]:
            a[int(a_b[i][0])] = -1
            a[int(a_b[i][1])] = -1
    elif a_b[i-1][0] == a_b[i][0]:
        if a[int(a_b[i][0])] == -1:
            if h[int(a_b[i][0])-1] >= h[int(a_b[i][1])-1]:
                a[int(a_b[i][1])] = -1
            
        else:
            if h[int(a_b[i][0])-1] > h[int(a_b[i][1])-1]:
                a[int(a_b[i][1])] = -1
            elif h[int(a_b[i][0])-1] < h[int(a_b[i][1])-1]:
                a[int(a_b[i][0])] = -1
            elif h[int(a_b[i][0])-1] == h[int(a_b[i][1])-1]:
                a[int(a_b[i][0])] = -1
                a[int(a_b[i][1])] = -1
    else:
        if h[int(a_b[i][0])-1] > h[int(a_b[i][1])-1]:
            a[int(a_b[i][1])] = -1
        elif h[int(a_b[i][0])-1] < h[int(a_b[i][1])-1]:
            a[int(a_b[i][0])] = -1
        elif h[int(a_b[i][0])-1] == h[int(a_b[i][1])-1]:
            a[int(a_b[i][0])] = -1
            a[int(a_b[i][1])] = -1
            

ans = a.count(0)
print(ans-1)

Submission status: Accepted

Solution code:
mounten_num, bridge_num = map(int, input().split())
mounten_higests = [0] + list(map(int, input().split()))
not_bad_mountens = ['x'] + ['o'] * mounten_num


# inputをさばく. 橋の架かっている展望台のうち、低いほうはgood_mountenではない
for i in range(bridge_num):
    a, b = map(int, input().split())
    if mounten_higests[a] <= mounten_higests[b]:
        not_bad_mountens[a] = 'x'
    if mounten_higests[a] >= mounten_higests[b]:
        not_bad_mountens[b] = 'x'

print(not_bad_mountens.count('o'))

Submission status: Accepted

Solution code:
N,M= list(map(int , input().split()))
H = list(map(int , input().split()))
A = []
B = []
for i in range(M):
    x,y=[int(i) for i in input().split()]
    A.append(x)
    B.append(y)
S = []
for j in range (M):
    if H[A[j]-1] > H[B[j]-1]:
        S.append(B[j])        
    elif H[A[j]-1] < H[B[j]-1]:
        S.append(A[j])
    else:
        S.append(A[j])
        S.append(B[j])
S = list(set(S))
print(N-len(S))

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
Hn = [int(i) for i in input().split()]

g = [[] for i in range(N)] 

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

i = 0
for row in g:
    if(len(row) != 0):
        g[i] = list(set(row))
    i = i + 1
  

i = 0
ans = 0
# 個々の展望台に接続された展望台について
for connected_obs in g:
    now_obs_height = Hn[i]
    conected_max_height = 0
    # 接続された展望台の最大値を得る
    for j in connected_obs:
        conected_max_height = max(conected_max_height, Hn[j-1])
    if(now_obs_height > conected_max_height or len(g) == 0):
        ans = ans + 1
    i = i + 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
N,M = [int(i) for i in readline().split()]
#H = [int(i) for i in readline().split()]
#AB = [[int(i) for i in readline().split()] for _ in range(M)]
H = {i+1:int(e) for i,e in enumerate(readline().split())}
AB = [[int(i) for i in readline().split()] for _ in range(M)]

ng = []

for a,b in AB:
  if H[a] < H[b]:
    ng += [a]
  elif H[a] > H[b]:
    ng += [b]
  else:
    ng += [a,b]
#print(ng)
print(N-len(set(ng)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

def check(p: int, h: list, ways: dict):
    for w in ways[p]:
        if h[p] <= h[w]:
            return False
    return True


def main():
    tmp = [int(i) for i in input().split()]
    n = tmp[0]
    m = tmp[1]

    ways = defaultdict(set)
    h = [0] + [int(i) for i in input().split()]
    for _ in range(m):
        tmp = [int(i) for i in input().split()]
        ways[tmp[0]].add(tmp[1])
        ways[tmp[1]].add(tmp[0])
    
    cnt = 0
    for i in range(1, n+1):
        if check(i, h, ways):
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
height = list(map(int,input().split()))
# print(height)
bridge = [[] for i in range(n)]

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

# print(bridge)
good = [None for i in range(n)]
# print(good)

flag = True
for i in range(n):
	flag = True
	if good[i] == None:
		# print(str(i+1)+'番目の展望台を調べます。')
		for tembo in bridge[i]:
			# print(str(tembo+1)+'番目の展望台につながっています。')
			if height[i] <= height[tembo]:
				# print(str(tembo+1)+'のほうがい高いので良くない')
				flag = False
		good[i] = flag
		if good[i]:
			for tembo in bridge[i]:
				good[tembo] = False

# print(good)
ans = 0
for x in good:
	if x:
		ans += 1
print(ans)

Submission status: Accepted

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

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

ans = sum(P)
print(ans)

Submission status: Accepted

Solution code:
import sys

if __name__ == "__main__":
    line1 = sys.stdin.readline().strip()
    param1 = line1.split(" ")
    n = int(param1[0])
    m = int(param1[1])
    h = [int(h_i) for h_i in sys.stdin.readline().strip().split(" ")]

    roads = [[] for i in range(n)]

    for i in range(m):
        data = [int(a) - 1 for a in sys.stdin.readline().strip().split(" ")]
        A = data[0]
        B = data[1]
    
        roads[A].append(B)
        roads[B].append(A)

    print(sum([
        1 if len(roads[i]) == 0 or (h[i] > max([ h[j] for j in roads[i]])) else 0
        for i in range(n)        
    ]))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
H = [int(i) for i in input().split()]

a = [0] * m
b = [0] * m
ans = [1]* n



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


for j in range(m):
    if H[a[j]-1] < H[b[j]-1]:
        ans[a[j]-1] = 0
    elif H[a[j]-1] > H[b[j]-1]:
        ans[b[j]-1] = 0
    elif H[a[j]-1] == H[b[j]-1]:
        ans[a[j]-1] = 0
        ans[b[j]-1] = 0


print(ans.count(1))

Submission status: Accepted

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

print(check.count(1))

Submission status: Accepted

Solution code:
a = input().split(" ")
N = eval(a[0])
M = eval(a[1])
b = input().split(" ")
hight_lst = list(map(eval, b))
lst = []
for i in range(N):
    lst.append(1)
for i in range(M):
    c = input().split(" ")
    c1 = eval(c[0]) - 1
    c2 = eval(c[1]) - 1
    if hight_lst[c1] > hight_lst[c2]:
        lst[c2] = 0
    elif hight_lst[c1] < hight_lst[c2]:
        lst[c1] = 0
    else:
        lst[c1] = 0
        lst[c2] = 0
count = 0
for i in lst:
    if i == 1:
        count += 1

print(count)

Submission status: Accepted

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

data = [0]*n
#print(h)
#print(data)
for i in range(m):
    a,b = map(int,input().split())
    k = max(data[a-1],h[b-1])
    l = max(h[a-1],data[b-1])
    data[a-1],data[b-1] =k,l

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, (input().split()))
h = list(map(int, input().split()))
root = [[] for i in range(n)]
count = 0
for i in range(m):
  a,b = map(int, input().split())
  root[a-1].append(h[b-1])
  root[b-1].append(h[a-1])
for i in range(n):
  if root[i] == []:
    count += 1
  elif h[i] > max(root[i]):
    count += 1
print(count)

Submission status: Accepted

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

H = input().split()

C = [0] * N

for MM in range(M):
    A, B = map(int,input().split())

    if int(H[A-1]) == int(H[B-1]):
        C[A-1] = 1
        C[B-1] = 1
    elif int(H[A-1]) > int(H[B-1]):
        C[B-1] = 1
    else :
        C[A-1] = 1

ANS = 0

for CC in C:
    if CC == 0:
        ANS += 1

print(ANS)

Submission status: Accepted

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

X = []
for i in range(M):
    X += [[int(x) for x in input().split()]]

same = []
temp = [1] * (N+1)
ans = 0


for j in range(M):
    if H[X[j][0]] > H[X[j][1]]:
        temp[X[j][1]] = 0
    elif H[X[j][0]] < H[X[j][1]]:
        temp[X[j][0]] = 0
    else:
        same = same +  [X[j][0], X[j][1]]

same = set(same)
ans = temp.count(1) - 1

for i in same:
    if temp[i] == 1:
        ans -=1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
heights = list(map(int,input().split()))
lose = []

for i in range(M):
  x, y = map(int, input().split())
  if heights[x - 1] > heights[y - 1]:
    lose.append(y)
  elif heights[x - 1] < heights[y - 1]:
    lose.append(x)
  elif heights[x - 1] == heights[y - 1]:
    lose.append(y)
    lose.append(x)

print(N - len(list(set(lose))))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
connected_li = [None] * N
is_alone_li = [True] * N
ans = 0

for _ in range(M):
    A, B = map(int, input().split())
    if connected_li[A - 1] is None:
        connected_li[A - 1] = [B - 1]
        connected_li[A - 1] = set(connected_li[A - 1])
    else:
        connected_li[A - 1].add(B - 1)

    if connected_li[B - 1] is None:
        connected_li[B - 1] = [A - 1]
        connected_li[B - 1] = set(connected_li[B - 1])
    else:
        connected_li[B - 1].add(A - 1)

for i in range(N):
    if connected_li[i] is None:
        ans += 1
    else:
        flg = True
        for idx in connected_li[i]:
            if H[i] <= H[idx]:
                flg = False
                break
        if flg:
            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)]

t={}
for i in range(n):
    t[i+1]=True
for x in ab:
    if h[x[0]-1] > h[x[1]-1]:
        t[x[1]] = False
    elif h[x[0]-1] < h[x[1]-1]:
        t[x[0]] = False
    else:
        t[x[0]] = False
        t[x[1]] = False
c = 0
for y in t.values():
    if y:
        c += 1
print(c)

Submission status: Accepted

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

ans = [[i] for i in h]

for i in path:
    ans[i[0]-1].append(h[i[1]-1])
    ans[i[1]-1].append(h[i[0]-1])


count = 0
for i in ans:
    if len(i)==1:
      count += 1
    elif i[0] == max(i) and i.count(i[0])==1:
      count +=1
print(count)

Submission status: Accepted

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

for i in range(m):
    a[i],b[i] = list(map(int, input().split(' ')))
    a[i] -= 1; b[i] -= 1
root = [[] for i in range(n)]

for i in range(m):
    root[a[i]] += [b[i]]
    root[b[i]] += [a[i]]

ret = [0 for i in range(n)]
for i,v in enumerate(root):
    flg = True
    for x in v:
        if h[i] > h[x]:
            flg = True
        else:
            flg = False
            break
    if flg:
        ret[i] += 1
print(len([1 for i in ret if i>0]))

Submission status: Accepted

Solution code:
N, M=map(int, input().split())
#s = [input().split() for i in range(Q)]

ans=[]

H = input().split()

for i in range(M):
    road=input().split()
    if int(H[int(road[0])-1])>int(H[int(road[1])-1]):
        ans.append(int(road[1]))
    elif int(H[int(road[0])-1])==int(H[int(road[1])-1]):
        ans.append(int(road[0]))
        ans.append(int(road[1]))
    else:
        ans.append(int(road[0]))

print(N-len(set(ans)))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
y=[]
for i in range(m):
  s,t=map(int,input().split())
  if x[s-1]<x[t-1]:
    y.append(s)
  elif x[s-1]>x[t-1]:
    y.append(t)
  else:
    y.append(s)
    y.append(t)
z=set(y)
print(n-len(z))

Submission status: Accepted

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

good = [1]*n

for _ in range(m):
    i, j = map(int, input().split())
    if h[i-1] == h[j-1]:
        good[i-1] = 0
        good[j-1] = 0
    elif h[i-1] > h[j-1]:
        good[j-1] = 0
    elif h[i-1] < h[j-1]:
        good[i-1] = 0
print(sum(good))

Submission status: Accepted

Solution code:
# == C ==
N, M = map(int, input().split()) # N個の展望台、M本の道
NoGoodTenbodai = set()
H = list(map(int, input().split())) # H[i]=展望台_iの標高
for i in range(M):
	A, B = map(int, input().split()) # 道_iが結ぶ展望台の組
	if H[A-1] > H[B-1]:
		NoGoodTenbodai.add(B)
	elif H[A-1] < H[B-1]:
		NoGoodTenbodai.add(A)
	else:
		NoGoodTenbodai.add(A)
		NoGoodTenbodai.add(B)
print(N-len(NoGoodTenbodai))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
H = list(map(int, input().split()))
A=[]
for i in range(M):
    A.append(list(map(int, input().split())))
result=[]
for i in range(N):
    result.append(1)

for j in A:
    # 自分より大きいものに説臆されていたらNG
    if H[j[0]-1] > H[j[1]-1]:
        result[j[1]-1]=0
    else:
        result[j[0]-1]=0
    if H[j[0]-1] == H[j[1]-1]:
        result[j[0]-1]=0
        result[j[1]-1]=0
#print(result)
print(result.count(1))

Submission status: Accepted

Solution code:
N, M = list(map(int,input().split()))
H_list = list(map(int,input().split()))
xy = [map(int, input().split()) for _ in range(M)]
x, y = [list(i) for i in zip(*xy)]

result = [True] * N
for i in range(M):
  if(H_list[x[i]-1] > H_list[y[i]-1]):
    result[y[i]-1] = False
  elif(H_list[x[i]-1] < H_list[y[i]-1]):
    result[x[i]-1] = False
  else:
    result[x[i]-1] = False
    result[y[i]-1] = False
print(result.count(True))