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:
import collections
def main():

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

    d = dict()
    c = collections.defaultdict(int)
    s = set()
    for _ in range(M):
        A, B = map(int, input().split())
        if A > B: A, B = B, A
        c[(A, B)] += 1
        s.add(A)
        s.add(B)

    for v in c:
        A, B = v[0], v[1]
        if A-1 not in d:
            d[A-1] = H[B-1]
        else:
            d[A-1] = max(H[B-1], d[A-1])

        if B-1 not in d:
            d[B-1] = H[A-1]
        else:
            d[B-1] = max(H[A-1], d[B-1])

    ans = 0
    for v in d:
        if H[v] > d[v]:
            ans += 1

    return ans + (N - len(s))

if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().strip().split()]
H = {str(i+1): int(j) for i, j in enumerate(input().strip().split())}
out = {str(i+1): 0 for i in range(N)}
for _ in range(M):
  h = input().strip().split()
  out[h[0]] += 1
  out[h[1]] += 1
  
  if H[h[0]] > H[h[1]] and out[h[0]]==1:
    out[h[0]] = 0
  if H[h[0]] < H[h[1]] and out[h[1]]==1:
    out[h[1]] = 0
print(len([k for k, v in out.items() if v==0]))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
lis=list(map(int,input().split()))
ans=0
anlis=[0]*N
for i in range(K):
  a,b=map(int,input().split())
  if lis[a-1]>lis[b-1]:
    anlis[b-1]=1
  elif lis[b-1]>lis[a-1]:
    anlis[a-1]=1
  else:
    anlis[a-1]=1
    anlis[b-1]=1
for i in range(N):
  if anlis[i]==0:
    ans+=1
print(ans)

Submission status: Accepted

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

H = [int(n) for n in input().split()]

A = []
B = []

p = {}
for m in range(M):
    a, b = [int(n) for n in input().split()]
    A.append(a)
    B.append(b)

    if H[a-1] >= H[b-1]:
        if b in p:
            p[b].append(a)
        else:
            p[b] = [a]
    if H[a-1] <= H[b-1]:
        if a in p:
            p[a].append(b)
        else:
            p[a] = [b]

s = 0
for i in range(N):
    if i + 1 not in p:
        s += 1

print(s)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    h_list = [0] + list(map(int, input().split()))
    is_good = [True for i in range(n + 1)]
    for i in range(m):
        a, b = map(int, input().split())
        if h_list[a] <= h_list[b]:
            is_good[a] = False
        if h_list[a] >= h_list[b]:
            is_good[b] = False
    print(sum(b for b in is_good[1:] if b))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h_list = list(map(int, input().split()))
michi = []
good = [1 for _ in range(n)]

for _ in range(m):
    a,b =map(int, input().split())
    if good[a-1]:
        if h_list[a-1] <= h_list[b-1]:
            good[a-1] = 0
    if good[b-1]:
        if h_list[a-1] >= h_list[b-1]:
            good[b-1] = 0

print(sum(good))

Submission status: Accepted

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

roots = [list(map(int, input().split())) for _ in range(m)]

ans = [True]*n
for j, k in roots:
    hj = lst[j-1]
    hk = lst[k-1]
    if hj == hk:
        ans[k-1] = False
        ans[j-1] = False

    elif hj > hk:
        ans[k-1] = False
    else:
        ans[j-1] = False

print(ans.count(True))

Submission status: Accepted

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

tmp=[0]*N

for li in S:
    A=li[0]-1
    B=li[1]-1

    if H[A]>=H[B]:
        tmp[B]=1
    if H[A]<=H[B]:
        tmp[A]=1

c=tmp.count(0)
print(c)

Submission status: Accepted

Solution code:
from collections import defaultdict


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst):
        self.graph[src].append((dst))

    def get_nodes(self):
        return self.graph.keys()


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

    g1 = Graph()
    for ab in AB:
        if H[ab[0]-1] >= H[ab[1]-1]:
            g1.add_edge(ab[1], ab[0])
        if H[ab[0]-1] <= H[ab[1]-1]:
            g1.add_edge(ab[0], ab[1])

    print(N-len(g1))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

graph = {n:set() for n in range(1,N+1)}
for _ in range(M):
    A, B = [int(n) for n in input().split()]
    graph[A].add(B)
    graph[B].add(A)

total = 0
for node in graph:
    if graph[node] == None:
        total += 1
    else:
        better = True
        for nbr in graph[node]:
            if heights[nbr-1] >= heights[node-1]:
                better = False
                break
        if better:
            total += 1

print(total)

Submission status: Accepted

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

Submission status: Accepted

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

route_dic = {i: set() for i in range(1, N+1)}
for a, b in AB_list:
    route_dic[a].add(b)
    route_dic[b].add(a)

ans = 0
for k, v in route_dic.items():
    flag = True
    for vv in v:
        if H[k-1] <= H[vv-1]:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

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

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

l = [1 for i in range(N)]
for ab in AB:
    a = ab[0]-1
    b = ab[1]-1

    if H_list[a] <= H_list[b]:
        l[a] = 0

    if H_list[b] <= H_list[a]:
        l[b] = 0

print(sum(l))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
Height = list(map(int,input().split()))
MichiList = []
cnt = 0
for _ in range(M):
    li = list(map(int,input().split()))
    MichiList.append(li)
IkeruList = []
for _ in range(N):
    IkeruList.append([])
for i in MichiList:
    a = i[0]
    b = i[1]
    IkeruList[a-1].append(Height[b-1])
    IkeruList[b-1].append(Height[a-1])
for i in range(N):
    if len(IkeruList[i]) == 0:
        cnt += 1
    else:
        if Height[i] > max(IkeruList[i]):
            cnt += 1
print(cnt)

Submission status: Accepted

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

L = []
for l in range(N):
    tmp=[]
    L.append(tmp)

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

cnt=0
for l in range(len(L)):
    good=True
    for t in range(len(L[l])):
        if H[l] <= H[L[l][t]]:
            good=False
    if good:
        cnt+=1

print(cnt)

Submission status: Accepted

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

maxs = [0 for _ in range(N)]
for i in range(M):
    a, b = [int(a) for a in input().split()]
    maxs[a-1] = max(maxs[a-1], H[b-1])
    maxs[b-1] = max(maxs[b-1], H[a-1])

ans = 0
for i in range(len(maxs)):
    if maxs[i] < H[i]:
        ans += 1

print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, M: int, H: "List[int]", A: "List[int]", B: "List[int]"):
    conns = [[] for _ in range(N)]
    ret = 0
    for i in range(M):
        conns[A[i] - 1].append(B[i] - 1)
        conns[B[i] - 1].append(A[i] - 1)
    for i in range(N):
        tmp = 0
        for con in conns[i]:
            if H[i] > H[con]:
                tmp += 1
        if tmp == len(conns[i]) or len(conns[i]) == 0:
            ret += 1
    print(ret)
    return

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]"
    X = []
    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())
H=list(map(int,input().split()))

ans=[True for _ in range(N)]

for _ in range(M):
    Ai,Bi=map(int,input().split())
    if H[Ai-1]>H[Bi-1]:
        ans[Bi-1]=False
    elif H[Ai-1]<H[Bi-1]:
        ans[Ai-1]=False
    else:
        ans[Ai-1]=False
        ans[Bi-1]=False

print(ans.count(True))

Submission status: Accepted

Solution code:
from sys import stdin

n, m = [int(x) for x in stdin.readline().rstrip().split()]
hn = list(map(int, input().split()))

route_map = {}


def add_routemap(a, b):
    if a not in route_map:
        route_map[a] = [b]
    else:
        route_map[a].append(b)


def add_route(a, b):
    add_routemap(a, b)
    add_routemap(b, a)


for i in range(1, m+1):
    a, b = [int(x) for x in stdin.readline().rstrip().split()]
    add_route(a, b)

#print(route_map)

sum = 0
for i in range(n):
    good = True
    me = hn[i]
    number = i+1
    if number in route_map:
        for j in range(len(route_map[number])):
            other = hn[route_map[number][j]-1]
            if me <= other:
                good = False
                break
    #print(number,good)
    if good:
        sum +=1

print(sum)

Submission status: Accepted

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

Submission status: Accepted

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

#print(ten)

kotae = 0

for i in range(n):
    ans = 1
    if len(ten[i]) == 0:
        pass
    else:
        for j in ten[i]:
            if h_list[i] > h_list[j]:
                pass
            else:
                ans = 0
    kotae += ans
    #print(i, kotae,ans)

print(kotae)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
d={}
k=0
r=0
for i in range(m):
    b,c=map(int,input().split())
    if b in d:
        d[b].append(c)
    else:
        d[b]=[c]
    if c in d:
        d[c].append(b)
    else:
        d[c]=[b]
for key,val in d.items():
    p=0
    if len(val)>0:
        for i in range(len(val)):
            if a[key-1]>a[val[i]-1]:
                p+=1
        if p==len(val):
            k+=1

print(k+n-len(d))

Submission status: Accepted

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

# 8 6 9 1 2 1
#  x     x

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
AB_lst = [0] * (N+1)
for i in range(N+1): AB_lst[i] = []
for i in range(M):
    A, B = map(int, input().split())
    AB_lst[A].append(B)
    AB_lst[B].append(A)
# print(AB_lst)
ans = 0
for i in range(1, N+1):
    flug = True
    for j in AB_lst[i]:
        if not (H[i-1] > H[j-1]):
            flug = False
    if flug:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = 4, 3
HRR = [1, 2, 3, 4]
ARR = [
    [1, 3],
    [2, 3],
    [2, 4],
]

N,M =  map(int,input().split())
HRR = list(map(int,input().split()))
ARR = []
for i in range(M):
    ARR.append(list(map(int,input().split())))


def calculate(n, m, hrr, arr):
    dict = {}
    for i in range(n):
        dict.__setitem__(i, True)

    for ar in arr:
        start = ar[0] - 1
        end = ar[1] - 1
        if hrr[start] > hrr[end]:
            dict.__setitem__(end, False)
        if hrr[start] == hrr[end]:
            dict.__setitem__(start, False)
            dict.__setitem__(end, False)

        if hrr[start] < hrr[end]:
            dict.__setitem__(start,False)


    print(sum(list(dict.values())))

calculate(N,M,HRR,ARR)

Submission status: Accepted

Solution code:
import collections as cc
I=lambda:list(map(int,input().split()))
n,m=I()
h=[0]+I()
ans=0
ar=[1]*(n)
for i in range(m):
    x,y=I()
    if h[x]==h[y]:
        ar[x-1]=0
        ar[y-1]=0
    else:
        if h[x]<h[y]:
            ar[x-1]=0
        else:
            ar[y-1]=0
print(ar.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 i in range(m)]

bad=[]
for i in ab:
  a,b=h[i[0]-1],h[i[1]-1]
  if a<b:
    bad+=[i[0]]
  elif a>b:
    bad+=[i[1]]
  else:
    bad+=[i[0],i[1]]
print(n-len(set(bad)))

Submission status: Accepted

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

Evaluation = [0] * N

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

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

print(count)

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())
    if h[a-1] > h[b-1]:
        c = b
        ans[c-1] = 0 
    elif h[a-1] < h[b-1]:
        c = a
        ans[c-1] = 0
    else:
        ans[a-1] = 0
        ans[b-1] = 0
print(sum(ans))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
H = list(map(int,input().split()))
 
rlist = {n:[] for n in range(1,N+1)}
cnt = 0
for m in range(1,M+1):
  A,B = map(int,input().split())
  rlist[A].append(B)
  rlist[B].append(A)
  
for k,v in rlist.items():
  if len(v) == 0:
    cnt += 1
  else:
    for i in v:
      if H[k-1] <= H[i-1]:
        break
    else:
      cnt += 1
      
print(cnt)

Submission status: Accepted

Solution code:
def task(n, m, h, a, b):
    roads = {}

    for i in range(1, n + 1):
        roads[i] = set()

    for i in range(0, m):
        roads[a[i]].add(b[i])
        roads[b[i]].add(a[i])

    total = 0
    for i in range(0, n):
        highest = True

        for road in roads[i + 1]:
            if h[road - 1] >= h[i]:
                highest = False
                break

        if highest:
            total += 1

    print(total)


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

task(n, m, h, a, b)

Submission status: Accepted

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

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

c = 0
for j in range(n):
  if len(l[j]) == 0:
    c += 1
  else:
    m = 0
    for k in l[j]:
      if h[j] <= h[k]:
        m = 1
        break
    if m == 0:

      c += 1
      
print(c)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=list(map(int,input().split()))
edge=[[] for _ in range(n)]
flg=[True]*n
d=dict()
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    if (a,b) in d or (b,a) in d:
        continue
    else:
        edge[a].append(b)
        edge[b].append(a)
        d[(a,b)]=0
        d[(b,a)]=0
ans=0
#print(edge)
for i in range(n):
    if not flg[i]:
        continue
    if len(edge[i])==0:
        ans+=1
    else:
        ok=True
        for e in edge[i]:
            if h[i]<=h[e]:
                flg[i]=False
                ok=False
            else:
                flg[e]=False
        if ok:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''

'''

def solve(h,adj):
	n = len(h)
	ans = [0]*n
	for i in range(n):
		if(ans[i] == 0):
			currH = h[i]
			f = 1
			z = 1
			for nn in adj[i]:
				f = 0
				if(h[nn] >= currH):
					z = 0
					break
				elif(h[nn] < currH):
					ans[nn] = -1
			if(z == 1 and f == 0 and ans[i] == 0):
				ans[i] = 1
	for i in range(n):
		if(len(adj[i]) == 0):
			ans[i] = 1
	return ans.count(1)

N,M = list(map(int, stdin.readline().rstrip().split()))
h = list(map(int, stdin.readline().rstrip().split()))
adj = [[] for i in range(N)]
for mm in range(M):
	a,b = list(map(int, stdin.readline().rstrip().split()))
	a -= 1
	b -= 1
	adj[a].append(b)
	adj[b].append(a)
ans = solve(h,adj)
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)]
c=[0]*n
for i , j in AB:
    if h[i-1]<=h[j-1]:
        c[i-1]=-10**10
    if h[j-1]<=h[i-1]:
        c[j-1]=-10**10
cnt=0
for i in c:
    if i == 0:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
# coding:utf-8

from collections import defaultdict

N, M = map(int, input().split(' '))
H = list(map(int, input().split(' ')))
H_flag = [True for _ in range(N)]
dic = defaultdict(list)

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

ans = 0
for k, v in dic.items():
    H_flag[k] = False
    maximum = H[k]
    for el in list(set(v)):
        if maximum <= H[el]:
            break
    else:
        ans += 1

print(ans + H_flag.count(True))

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)]
gr=[[] for i in range(n)]
for i in range(m):
    gr[ab[i][0]-1].append(ab[i][1])
    gr[ab[i][1]-1].append(ab[i][0])
cnt=0
for i in range(n):
    for j in gr[i]:
        if h[i]<=h[j-1]:
            break
    else:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
[n,m]=list(map(int,input().split()))
hight=list(map(int,input().split()))
road=[]
for i in range(m):
    road.append(sorted(list(map(int,input().split()))))

check=[1]*n #1ならok,0ならng
for i in range(m):
    if hight[road[i][0]-1]>hight[road[i][1]-1]:
        check[road[i][1]-1]=0
    if hight[road[i][0]-1]<hight[road[i][1]-1]:
        check[road[i][0]-1]=0
    if hight[road[i][0]-1]==hight[road[i][1]-1]:
        check[road[i][0]-1]=0
        check[road[i][1]-1]=0

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

print(ans)

Submission status: Accepted

Solution code:

from collections import deque

N, M = map(int, input().split())
H = [int(x) for x in input().split()]
AB = [deque([]) for _ in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    AB[A-1].append(H[B-1])
    AB[B-1].append(H[A-1])
ans = 0
for i in range(N):
    if len(AB[i]) == 0:
        ans += 1
        continue
    if H[i] > max(AB[i]):
        ans += 1
print(ans)

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):
    tmp=[int(i) for i in input().split()]
    a.append(tmp[0]-1)
    b.append(tmp[1]-1)

isGood=[1]*n
for i in range(m):
    if h[a[i]] >= h[b[i]]:
        isGood[b[i]] = 0
    if h[a[i]] <= h[b[i]]:
        isGood[a[i]] = 0

ans=sum(isGood)
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h = list(map(int,input().split()))
j = set()
ab = [list(map(int,input().split()))for i in range(m)]
for i in range(m):
    #a,b = map(int,input().split())
    a = ab[i][0]
    b = ab[i][1]
    if h[a-1] > h[b-1]:
        j.add(b)
    elif h[b-1] > h[a-1]:
        j.add(a)
    else:
        j.add(a)
        j.add(b)

print(n-len(j))

Submission status: Accepted

Solution code:
n, m = (int(x) for x in input().split())
sh = input().split(" ")
h = []
for s in sh:
    h.append([int(s), []])
for i in range(m):
    a, b = (int(x) for x in input().split())
    h[a - 1][1].append(b - 1)
    h[b - 1][1].append(a - 1)
cnt = n
for i in h:
    for j in i[1]:
        if i[0] <= h[j][0]:
            cnt -= 1
            break

print(cnt)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    N, M = map(int, input().split())
    H = list(map(int, input().rstrip().split(' ')))
    nodes = [[] for i in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        nodes[a-1].append(b-1)
        nodes[b-1].append(a-1)
    #print(nodes)
    ans = 0
    for i, children in enumerate(nodes):
        h = H[i]
        result = 1
        for c in children:
            h_ = H[c]
            if h <= h_:
                result = 0
                break
        ans += result
    print(ans)

Submission status: Accepted

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

N = NM[0]; M = NM[1]

H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

result = [0]*N

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

print(N-sum(result))

Submission status: Accepted

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

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

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

for pair in listM:
    if listH[pair[0]-1] > listH[pair[1]-1]:
        listC[pair[1]-1] -= 1
    elif listH[pair[0]-1] < listH[pair[1]-1]:
        listC[pair[0]-1] -= 1
    else:
        listC[pair[1]-1] -= 1
        listC[pair[0]-1] -= 1
        
cnt = 0

for i in listC:
    if i == 1:
        cnt += 1
        
print(cnt)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
H = list(map(int, input().split()))
t = {}
for n in range(1, N+1):
    t[n] = H[n-1]

r = set()
for m in range(M):
    A, B = list(map(int, input().split()))
    if t[A] < t[B]:
        r.add(A)
    elif t[B] < t[A]:
        r.add(B)
    else:
        r.add(A)
        r.add(B)
print(len(set(t.keys()) - r))

Submission status: Accepted

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

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

cnt = 0

for i, lst in enumerate(road):
	for j in lst:
		if H[i] <= H[j]:
			break
	else:
		cnt += 1

print(cnt)

Submission status: Accepted

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

gooddict={i:1 for i in range(1,n+1)}

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
h = [int(i) for i in input().split()]
lose = [False]*n
ans = n
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    if lose[u] and lose[v]:
      continue
    elif lose[u] and not lose[v]:
      if h[v] > h[u]:
        continue
      else:
        lose[v] = True
        ans -= 1
    elif not lose[u] and lose[v]:
      if h[u] > h[v]:
        continue
      else:
        lose[u] = True
        ans -= 1
    elif not lose[u] and not lose[v]:
      if h[u] > h[v]:
        lose[v] = True
        ans -= 1        
      elif h[v] > h[u]:
        lose[u] = True
        ans -= 1        
      elif h[v] == h[u]:
        lose[u] = True
        lose[v] = True
        ans -= 2
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
H = [int(a) for a in input().split()]
ans= [1] * n
for i 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[a-1] = 0
        ans[b-1] = 0
    elif H[a-1] < H[b-1]:
        ans[a-1] = 0
print(sum(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
H = [int(s) for s in input().split()]

edges = defaultdict(list)

for i in range(M):
    w = 1
    u, v = map(int, input().split())
    edges[u-1].append((v-1, w))
    edges[v-1].append((u-1, w))

# print(edges)

ans = 0
for i in range(N):
    c = True
    for v, w in edges[i]:
        if H[i] <= H[v]:
            c = False
            break
    ans += 1 if c else 0

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
AB = dict()
for _ in range(M):
    a, b = map(int, input().split())
    if a not in AB:
        AB[a] = [H[b-1]]
    else:
        AB[a].append(H[b-1])

    if b not in AB:
        AB[b] = [H[a-1]]
    else:
        AB[b].append(H[a-1])

cnt = 0
for n in range(1, N+1):
    if (n not in AB.keys()) or (max(AB[n]) < H[n-1]):
        cnt += 1

print(cnt)

Submission status: Accepted

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

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

ans=graph.count(0)
print(ans)

Submission status: Accepted

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

count = N
for i in range(M):
    a, b = map(int, input().split())
    if H[a - 1] <= H[b - 1] and flag[a - 1] is False:
        flag[a - 1] = True
        count -= 1
    if H[a - 1] >= H[b - 1] and flag[b - 1] is False:
        flag[b - 1] = True
        count -= 1

print(count)

Submission status: Accepted

Solution code:
i = list(map(int, input().split()))
high = list(map(int, input().split()))
good = [0]*i[0]
for j in range(i[1]):
    k = list(map(int, input().split()))
    if high[k[0]-1]>=high[k[1]-1]:
        good[k[1]-1]=1
    if high[k[0]-1]<=high[k[1]-1]:
        good[k[0]-1]=1
print(good.count(0))

Submission status: Accepted

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

Submission status: Accepted

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

H = list(map(int, input().split(" ")))
road_list = [[] for _ in range(N)]
for i in range(M):
	a_i, b_i = list(map(int, input().split(" ")))
	road_list[a_i-1].append(H[b_i-1])
	road_list[b_i-1].append(H[a_i-1])
good_hills = 0
for i, road in enumerate(road_list):
	if len(road) == 0:
		good_hills += 1
	elif H[i] > max(road):
		good_hills += 1

print(good_hills)