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:
# coding: utf-8

n, m = list(map(int, input().split()))
hs = list(map(int, input().split()))
hs = [-1] + hs
es = [list(map(int, input().split())) for _ in range(m)]

# "同じ展望台の組を結ぶ道が複数あることもある。"
ed = {}
for a, b in es:
    if a not in ed:
        ed[a] = set([b])
    else:
        ed[a].add(b)
    if b not in ed:
        ed[b] = set([a])
    else:
        ed[b].add(a)

#print(ed)
cnt = 0
for s in range(1, n+1):
    #print ('start point %s:' % s)
    if s not in ed:
        #print('=> isolate')
        cnt += 1
    else:
        mx = max(hs[e] for e in ed[s])
        pred = hs[s] > mx
        #print ('h = %s, mx = %s' % (hs[s], mx))
        if pred:
            #print('xx')
            cnt += 1

print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = [int(i) for i in input().split()]
path = [[] for i in range(n)]
set_path = set()
for i in range(m):
    a, b = map(int, input().split())
    path[a - 1].append(b - 1)
    path[b - 1].append(a - 1)
    set_path |= set((a - 1, b - 1))
cnt = n - len(set_path)
path_ = {int(i) for i in range(n)}
for i in set_path:
    if max([h[j] for j in path[i]]) < h[i]:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
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())))

J=[0]*N
for i in range(M):
    if H[AB[i][0]-1]<H[AB[i][1]-1]:
        J[AB[i][0]-1]+=1
    elif H[AB[i][0]-1]==H[AB[i][1]-1]:
        J[AB[i][0]-1]+=1
        J[AB[i][1]-1]+=1    
    else:
        J[AB[i][1]-1]+=1
c=0
for i in J:
    if i == 0:
        c+=1

print(c)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
height = list(map(int,input().split()))
arr = []

for i in range(m):
   x, y = map(int,input().split())
   height_x = height[x-1]
   height_y = height[y-1]
   if height_x > height_y:
      arr.append(y)
   elif height_x < height_y:
      arr.append(x)
   else:
      arr.append(x)
      arr.append(y)
arr = list(set(arr))
print(n-len(arr))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = list(map(int,input().split()))
d = {}
each = []
for i in range(m):
	sou,des = map(int,input().split())
	each.append(sou)
	each.append(des)
	if sou not in d:
		d[sou] = [des]
	else:
		d[sou].append(des)
	if des not in d:
		d[des] = [sou]
	else:
		d[des].append(sou)
#print(d)
#print(dic)
count = 0
for i in d:
	flag = True
	for j in d[i]:
		if l[i-1] <= l[j-1]:
			flag = False
			break
	if flag:
		count += 1
count += (n - len(set(each)))
print(count)

Submission status: Accepted

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

#j[x][y]は、x個目の灯台からたどり着ける場所を列挙している。
for i in range(M):
  for j in range(2):
    judge[A[i][j]-1].append(A[i][j-1])
    
for k in range(N):
  for l in range(len(judge[k])):
    if H[k] > H[judge[k][l]-1]:
      continue
      
    else:
      ans[k] -= 1
      break
      
print(sum(ans))

Submission status: Accepted

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m = mi()
    L = lmi()
    height = [[elm, i] for i, elm in enumerate(L)]
    num_to_h = dict()
    for i, elm in enumerate(height):
        h, num = elm
        num_to_h[num] = h

    good_predicate = [True] * n
    path = [lmi_0() for _ in range(m)]
    for i, j in path:
        i_h, i_j = num_to_h[i], num_to_h[j]
        if i_h == i_j:
            good_predicate[i] = False
            good_predicate[j] = False
        elif i_h < i_j:
            good_predicate[i] = False
        else:
            good_predicate[j] = False
        # print(f"{i} {j}")
        # print(good_predicate)
    # print(good_predicate)
    cnt = 0
    for elm in good_predicate:
        if elm:
            cnt += 1
    print(cnt)




if __name__ == "__main__":
    main()

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)]
l=[0]*n
for i in range(m):
    if h[ab[i][0]-1]>h[ab[i][1]-1]:
        l[ab[i][1]-1]+=1
    elif h[ab[i][0]-1]<h[ab[i][1]-1]:
        l[ab[i][0]-1]+=1
    else:
        l[ab[i][1]-1]+=1
        l[ab[i][0]-1]+=1
print(l.count(0))

Submission status: Accepted

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


def solve(N: int, M: int, H: "List[int]", A: "List[int]", B: "List[int]"):
    score = [0] * N
    for i in range(M):
        a = H[A[i] - 1]
        b = H[B[i] - 1]

        score[A[i] - 1] = max(score[A[i] - 1], b)
        score[B[i] - 1] = max(score[B[i] - 1], a)

    count = 0
    for i in range(N):
        if H[i] > score[i]:
            count += 1

    print(count)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    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))
    solve(N, M, H, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
Goodtower=["1"]*N

H=list(map(int,input().split()))
for i in range(M):
    A,B=map(int,input().split())
    if H[A-1] > H[B-1]:
        Goodtower[B-1]=0
        #print(B+"is NOT good!")
    elif H[A-1] < H[B-1]:
        Goodtower[A-1]=0
        #print(str(A)+"is NOT good!")
    else:
        Goodtower[A-1]=0
        Goodtower[B-1]=0
        #print(str(A)+"is NOT good!")
        #print(str(B)+"is NOT good!")
print(Goodtower.count("1"))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=list(map(int,input().split()))
d={}
for i in range(n):
	d[i+1]=[]
while m:
	m-=1
	a,b=map(int,input().split())
	d[a].append(b)
	d[b].append(a)
c=0
for i in d:
	f=0
	for j in d[i]:
		if l[j-1]>=l[i-1]:
			f=1
			break
	if f==0:
		c+=1
		#print(i)
	
print(c)

Submission status: Accepted

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

weak=[]
for i in range(M):
    An,Bn =map(int,input().split())
    if H_n[An-1] < H_n[Bn-1]:
        weak.append(An)
    elif H_n[An-1] == H_n[Bn-1]:
        weak.append(An)
        weak.append(Bn)
    else:
        weak.append(Bn)

print(N -len(set(weak)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = input().split(" ")
N, M = int(N), int(M)
H = [int(h) for h in input().split(" ")]
A = []
B = []
TF = [True] * N
for i in range(M):
    a, b = input().split(" ")
    a, b = int(a), int(b)
    if H[a-1] > H[b-1]:
        if TF[b-1]:
            TF[b-1] = False
    elif H[b-1] > H[a-1]:
        if TF[a-1]:
            TF[a-1] = False
    else:
        TF[b-1] = False
        TF[a-1] = False
            
print(sum(TF))

Submission status: Accepted

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

for i in range(m):
    ab.append(list(map(int, input().split())))

f = [1] * len(h)

for i,abi in enumerate(ab):
    if h[abi[0]-1] <= h[abi[1]-1]:
        f[abi[0]-1] = 0
    if h[abi[0]-1] >= h[abi[1]-1]:
        f[abi[1]-1] = 0

print(sum(f))

Submission status: Accepted

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

import networkx as nx
G = nx.Graph()
for i in range(k[0]):
  G.add_node(i +1)
for i in m:
  G.add_edge(i[0],i[1])
re = 0
for i in list(G.nodes):
  if len(list(nx.all_neighbors(G, i))) != 0:
    max_height = max([h[x - 1] for x in list(nx.all_neighbors(G, i))])
    if h[i-1] > max_height:
      re +=1
  else:
    re +=1
print(re)

Submission status: Accepted

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

import collections
c=collections.Counter(ll)
print(n-len(c))

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)]

flag = [1]*n

for i in ab:
  if h[i[0]-1] > h[i[1]-1]:
    flag[i[1]-1] = 0
  elif h[i[0]-1] < h[i[1]-1]:
    flag[i[0]-1] = 0
  else:
    flag[i[1]-1] = 0
    flag[i[0]-1] = 0

print(flag.count(1))

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)]

good = [True]*N
for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    if H[a] >= H[b]:
        good[b] = False
    if H[b] >= H[a]:
        good[a] = False

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N, M = map(int, input().split())
HList = list(map(int, input().split()))
AList = [list(map(int, input().split())) for i in range(M)]

anslist = [0] * N
#print(AList[0])
i=0    
while i<M:
    checkA = AList[i][0]
    checkB = AList[i][1]
    #print(HList[checkA-1])
    if HList[checkA-1] < HList[checkB-1]:
        anslist[checkA-1]="x"
    elif HList[checkA-1] > HList[checkB-1]:
        anslist[checkB-1]="x"
    else:
        anslist[checkA-1]="x"
        anslist[checkB-1]="x"
        
    i+=1
print(anslist.count(0))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def main():
    N,M = map(int, input().split())
    H = list(map(int, input().split()))
    nodes = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        nodes[a-1].append(b-1) 
        nodes[b-1].append(a-1)
    count = 0
    for i in range(N):
        res = True
        if len(nodes[i]) == 0:
            count += 1
            continue
        for n in nodes[i]:
            res = res and (H[n] < H[i])
        count += int(res)
    print(count)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
height = list(map(int, input().split()))
good = [True] * N

for i in range(M):
    A, B = map(int, input().split())
    if height[A-1] < height[B-1]:
        good[A-1] = False
    elif height[A-1] > height[B-1]:
        good[B-1] = False
    else:
        good[A-1] = False
        good[B-1] = False

print(good.count(True))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
height = list(map(int,input().split()))
lst = [0] * n
for j in range(m):
  a,b=map(int,input().split())
  if height[a-1]<height[b-1]:
    if height[b-1] <0:
      lst[a-1]=-100
    else:
      lst[a-1]=-100
      lst[b-1]+=1
  elif height[a-1]>height[b-1]:
    if height[a-1]<0:
      lst[b-1]=-100
    else:
      lst[a-1]+=1
      lst[b-1]=-100
  elif height[a-1]==height[b-1]:
    lst[a-1] = -100
    lst[b-1] = -100
cnt = 0
for k in range(n):
  if lst[k]>=0:
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
n, m = [int(elem) for elem in input().split()]
h_lst = [int(elem) for elem in input().split()]

res = [1] * n

for i in range(m):
    a, b = [int(elem) for elem in input().split()]
    if h_lst[a-1] > h_lst[b-1]:
        if res[b-1] != 0:
            res[b-1] -= 1
    elif h_lst[a-1] < h_lst[b-1]:
        if res[a-1] != 0:
            res[a-1] -= 1
    else:
        if res[a-1] != 0:
            res[a-1] -= 1
        if res[b-1] != 0:
            res[b-1] -= 1
print(sum(res))

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
height = list(map(int,input().split()))
route = [set() for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    if not (b - 1) in route[a - 1]:
        route[a - 1].add(b - 1)
        route[b - 1].add(a - 1)

out = 0
for i in range(n):
    if len(route[i]) == 0:
        out += 1
    else:
        flg = 1
        for j in route[i]:
            if height[i] <= height[j]:
                flg = 0
                break
        if flg == 1:
            out += 1

print(out)

Submission status: Accepted

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

Submission status: Accepted

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

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

print(ans.count(0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
d = dd(list)

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

ans = []
for i in range(n):
    flg = True
    for nb in d[i+1]:
        if h[i] <= h[nb-1]:
            flg = False
    if flg or len(d[i+1]) == 0:
        ans.append(i+1)

print(len(ans))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H_ = list(map(int,input().split()))
H = [0]
H.extend(H_)
D = dict()
for i in range(M):
    t_ = list(map(int,input().split()))
    if t_[0] not in D.keys():
        D[t_[0]] = [t_[1]]
    else:
        D[t_[0]].append(t_[1])
    if t_[1] not in D.keys():
        D[t_[1]] = [t_[0]]
    else:
        D[t_[1]].append(t_[0])
ret = list()
for v in D.keys():
    L = D[v]
    for i in range(len(L)):
        if H[v] <= H[L[i]]:
            break
        if i == len(L) - 1:
            ret.append(v)
num = N - len(D.keys()) + len(ret)
print(num)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
h = input().split()
e = [1]*n
ans = 0

for i in range(n):
  h[i] = int(h[i])
#
#print(h)

for i in range(m):
  a,b = map(int, input().split())
  if h[a-1] > h[b-1]:
    e[b-1] = 0
  elif h[a-1] < h[b-1]:
    e[a-1] = 0
  else:
    e[a-1] = 0
    e[b-1] = 0
#
#print(e)

for i in e:
  if i==1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
height = list(map(int, input().split()))
observetry = list(range(1, n+1))
lose = []

for i in range(m):
    a, b = map(int, input().split())
    if height[a-1] == height[b-1]:
        lose.append(a)
        lose.append(b)
    elif height[a-1] > height[b-1]:
        lose.append(b)
    else:
        lose.append(a)

ans = list(set(observetry) - set(lose))
print(len(ans))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
l1=[]
l2=[]
l=[0]*n
for i in range(m):
  a,b=map(int,input().split())
  if a>b:
    c=a
    a=b
    b=c
  k=[a,b]
  l1.append(k)
  c=a
  a=b
  b=c
  k=[a,b]
  l2.append(k)
l1.sort()
l2.sort(reverse=True)
for i in l1:
  if h[i[0]-1]<=h[i[1]-1]:
    l[i[0]-1]+=1
for i in l2:
  if h[i[0]-1]<=h[i[1]-1]:
    l[i[0]-1]+=1
print(l.count(0))

Submission status: Accepted

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

roads = []
for i in range(N):
    roads.append([])
    
for i in range(M):
    r = list(map(lambda x: int(x)-1, input().split()))
    roads[r[0]].append(r[1])
    roads[r[1]].append(r[0])

goodcount = 0
for i in range(len(H)):
    isgood = True
    for r in roads[i]:
        if H[i] <= H[r]:
            isgood = False
    if isgood:
        goodcount += 1

print(goodcount)

Submission status: Accepted

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

rem_list = []

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

print(n-len(set(rem_list)))

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    s = input().rstrip().split(' ')
    N,M = int(s[0]), int(s[1])
    adj = []
    for _ in range(N):
        adj.append(set())
    s = input().rstrip().split(' ')
    height = [int(elem) for elem in s]
    for _ in range(M):
        s = input().rstrip().split(' ')
        A,B = int(s[0])-1, int(s[1])-1
        adj[A].add(B)
        adj[B].add(A)


    count = 0
    for i in range(N):
        flag = True
        for adj_n in adj[i]:
            if height[adj_n] >= height[i]:
                flag = False
                break

        if flag == True:
            count += 1

    print(count)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=list(map(int,input().split()))
Graph=[[] for i in range(N)]
isGood = [1]*N
for i in range(M):
  a,b=map(int,input().split())
  Graph[a-1].append(b)
  Graph[b-1].append(a)
# print(Graph)
for i in range(N):
  for j in Graph[i]:
    if H[i]<=H[j-1]:
      isGood[i]=0
# print(H)
print(sum(isGood))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
x=[1]*n
for i in range(m):
  a,b=map(int,input().split())
  A=h[a-1]
  B=h[b-1]
  if A!=B:
    z=min(A,B)
    if z==A:
       x[a-1]=0
    else:
       x[b-1]=0
  else:
    x[a-1]=0
    x[b-1]=0
  
print(sum(x))

Submission status: Accepted

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

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

# print(ans)
print(ans.count(0))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h = list(map(int,input().split()))
li = []
for _ in range(m):
    li.append(list(map(int,input().split())))
counted_list = [0] * n #0ならオッケー、1ならアウト
for i in range(m):
    if h[li[i][0]-1] > h[li[i][1]-1]:
        counted_list[li[i][1]-1] = 1
    elif h[li[i][0]-1] == h[li[i][1]-1]:
        counted_list[li[i][1]-1] = 1
        counted_list[li[i][0]-1] = 1
    else:
        counted_list[li[i][0]-1] = 1
print(counted_list.count(0))

Submission status: Accepted

Solution code:
num_obs, num_roads = list(map(int, input().split()))


class Obs:
    def __init__(self, elevation, idd):
        self.elevation = elevation
        self.roads_connecting = []
        self.id = idd

    def __repr__(self):
        return "ID:"+str(self.id)+" E:"+str(self.elevation)+"m"


heights = input().split()

observatories = []
i = 1
for h in heights:
    observatories.append(Obs(int(h), i))
    i += 1

for j in range(num_roads):
    road = list(map(int, input().split()))
    observatories[road[0]-1].roads_connecting.append(observatories[road[1]-1])
    observatories[road[1]-1].roads_connecting.append(observatories[road[0]-1])

good_boys = 0

for o in observatories:
    is_good = True
    if len(set(o.roads_connecting)) == 0:
        good_boys += 1
        continue
    for subo in set(o.roads_connecting):
        if subo.elevation >= o.elevation and subo.id != o.id:
            is_good = False
            break
    if is_good:
        good_boys += 1

print(good_boys)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
Hn = list(map(int, input().split()))
abn = [list(map(int, input().split())) for _ in range(m)]
pool = [[] for h in Hn]
for ab in abn:
    pool[ab[0]-1].append(Hn[ab[1]-1])
    pool[ab[1]-1].append(Hn[ab[0]-1])
ans = 0
for i in range(n):
    if len(pool[i]) == 0:
        ans += 1
    else:
        if max(pool[i]) < Hn[i]:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)


def main():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))

    good = [True] * N

    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if H[a] < H[b]:
            good[a] = False
        elif H[a] > H[b]:
            good[b] = False
        else:
            good[a] = False
            good[b] = False

    print(good.count(True))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

print(result.count(1) + route.count(0))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

N, M = MII_split()
Heightis = LII_split()

searched = [False for _ in range(N)]
group_indicies = [-1 for _ in range(N)]

count = 0
groups = []
# while searched.count(False) > 0:
id_count = 0
neighbors = dict()
for _ in range(M):
    A, B = MII_split()
    searched[A - 1] = searched[B - 1] = True
    if A - 1 in neighbors:
        neighbors[A - 1].append(B - 1)
    else:
        neighbors[A - 1] = [B - 1]
    if B - 1 in neighbors:
        neighbors[B - 1].append(A - 1)
    else:
        neighbors[B - 1] = [A - 1]
for k, v in neighbors.items():
    n_heights = []
    for i in v:
        n_heights.append(Heightis[i])
    ma = max(n_heights)
    if ma < Heightis[k]:
        count += 1

# if not searched[A - 1] and not searched[B - 1]:
#     searched[A - 1] = True
#     searched[B - 1] = True
#     group_indicies[A - 1] = group_indicies[B - 1] = id_count
#     count += 1
#     id_count += 1
# elif searched[A - 1] and searched[B - 1]:
#     if group_indicies[A - 1] != group_indicies[B - 1]:
#         new_g_id = group_indicies[A - 1]
#         group_indicies = [new_g_id if i == group_indicies[B - 1] else i for i in group_indicies]
#         count -= 1
# elif not searched[A - 1]:
#     searched[A - 1] = True
#     group_indicies[A - 1] = group_indicies[B - 1]
# elif not searched[B - 1]:
#     searched[B - 1] = True
#     group_indicies[B - 1] = group_indicies[A - 1]

print(count + searched.count(False))

Submission status: Accepted

Solution code:
import collections
n,m = list(map(int,input().split()))
tower_high = list(map(int,input().split()))
good_tower = [1]*n

def check_tower(a,b):
    if tower_high[a]<tower_high[b]:
        good_tower[a]=0
    elif tower_high[a] > tower_high[b]:
        good_tower[b]=0
    else:
        good_tower[a]=0
        good_tower[b]=0

for i in range(m):
    a,b=list(map(int,input().split()))
    check_tower(a-1,b-1)
print(good_tower.count(1))

Submission status: Accepted

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

d = {}

for i in range(N):
    d[i+1] = H[i]

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

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

    if H[B-1] <= H[A-1]:
        d[B] = 0

print(N - list(d.values()).count(0))

Submission status: Accepted

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

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


count = 0
for i in range(N):
    flag = 0
    for j in range(len(L[i])):
        if H[i] <= H[L[i][j]-1]:
            flag = 1
            break
    if flag == 0:
        count += 1
print(count)

Submission status: Accepted

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

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

ans = 0
for i,r_l in enumerate(road):
    cnt = 0
    if not r_l:
        ans+=1
        continue
    for r in r_l:

        if H[i] > H[r]:
            cnt +=1
    if cnt == len(r_l):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
 
high_list = list(map(int, input().split()))
check_list = [1]*N
 
for i in range(M):
  a_, b_ = map(int, input().split())
  if high_list[a_-1] < high_list[b_-1]:
    check_list[a_-1] = 0
  elif high_list[a_-1] > high_list[b_-1]:
    check_list[b_-1] = 0
  elif high_list[a_-1] == high_list[b_-1]:
    check_list[a_-1] = 0
    check_list[b_-1] = 0
 
print(sum(check_list))