Problem:


Score : 300 points

Problem Statement

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

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

How many good observatories are there?

Constraints

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq H_i \leq 10^9

1 \leq A_i,B_i \leq N

A_i \neq B_i

Multiple roads may connect the same pair of observatories.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of good observatories.

Sample Input 1

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

Sample Output 1

2

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

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

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

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

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

Sample Input 2

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

Sample Output 2

3



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


Sample output:
2

Submission status: Accepted

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

for i in range(m):
  a,b = map(int, input().split())
  high_a = h[a-1]
  high_b = h[b-1]
  if high_a > high_b:
    good_tower[b-1] = 0
  elif high_b > high_a:
    good_tower[a-1] = 0
  elif high_a == high_b:
    good_tower[b-1] = 0
    good_tower[a-1] = 0
    
print(sum(good_tower))

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
H = list(map(int, input().split()))
adj = defaultdict(set)
for i in range(M):
    a, b = map(int, input().split())
    adj[a-1].add(H[b-1])
    adj[b-1].add(H[a-1])
ans = 0
for i in range(N):
    adj[i].add(-1)
    if H[i] > max(adj[i]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def ma(li):
    # ループごとにifで大小比較
    max_num = 0
    for i in li:
        if max_num < i:
            max_num = i
    return max_num

def appen(li,yousa):
    li.append(yousa)
    return li
    
def main():
    res=0
    n,m=map(int,input().split())
    h=list(map(int,input().split()))
    
    a=[list(map(int,input().split())) for i in range(m)]
    f=[]
    for i in range(n):
        f.append([0])
    for i in a:
        f[i[0]-1].append(h[i[1]-1])
        f[i[1]-1].append(h[i[0]-1])
    p=-1
    for i in f:
        p+=1
        if len(i)==1:
            res+=1
        elif ma(i)<h[p]:
            res+=1
        else:
            continue

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

res = [1 for i in range(n) ]
for i in range(m):
    con = input().split()
    con = [int(ele) for ele in con]
    
    id1 = con[0] - 1
    id2 = con[1] - 1
    
    if res[id1] == 1:
        res[id1] = int(Hs[id2] < Hs[id1])
    if res[id2] ==1:
        res[id2] = int(Hs[id1] < Hs[id2])

print(sum(res))

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)]
list = [{} for _ in range(N)]
for x in AB:
    if x[1]-1 not in list[x[0]-1].keys():
        list[x[0]-1][x[1]-1] = 1
    if x[0]-1 not in list[x[1]-1].keys():
        list[x[1]-1][x[0]-1] = 1
#print(list)
ans = 0
for n, x in enumerate(list):
    cand = [H[i] for i in x.keys()]
    flag = 1
    for t in cand:
        if H[n] <= t:
            flag = 0
            break
    if flag == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
h=[int(i) for i in input().split()]
ansl=[]
dic={i:0 for i in range(a)}
aans=[]
for i in range(b):
    c,d=map(int,input().split())
    if True:
        ch=h[c-1]
        dh=h[d-1]
        if ch==dh:
            if dic[c-1]==0:
                ansl.append(c-1)
                dic[c-1]+=1
            if dic[d-1]==0:
                ansl.append(d-1)
                dic[d-1]+=1
        else:
            if ch<dh:
                if dic[c-1]==0:
                    ansl.append(c-1)
                    dic[c-1]+=1
            else:
                if dic[d-1]==0:
                    ansl.append(d-1)
                    dic[d-1]+=1
        aans.append([c,d])
print(a-len(ansl))

Submission status: Accepted

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

cnt = 0
tendai_hight = {}
tendai_good = {}

for i, h in enumerate(H_list):
    tendai_hight[i+1] = h
    tendai_good[i+1] = 0
    
# 道の数だけループ
while cnt < M:
    cnt += 1
    A, B = map(int, input().split())
    # 比較して低い方に負けフラグ1を立てる
    if tendai_hight[A] < tendai_hight[B]:
        tendai_good[A] = 1
    if tendai_hight[A] > tendai_hight[B]:
        tendai_good[B] = 1       
    # 比較して同じならば両方に負けフラグ1を立てる
    if tendai_hight[A] == tendai_hight[B]:
        tendai_good[A] = 1
        tendai_good[B] = 1
        
result = [key for key ,value in tendai_good.items() if value != 1]
print(len(result))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
h=[int(w) for w in input().split()]
x=[0]*(n)
for i in range(m):
    a,b=map(int,input().split())
    
    x[a-1]=max(h[b-1],x[a-1])
    x[b-1]=max(h[a-1],x[b-1])
        
ans=0
for i in range(n):
    if (h[i]>x[i]) or x[i]==0:
        ans+=1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

r = [0]
for i in range(n):
    r.append(set())

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

ans = 0
for i in range(1, n+1):
    if len(r[i]) == 0:
        ans += 1
        continue
    hmax = h[i-1]
    flag = True
    for j in r[i]:
        if h[j-1] == h[i-1]: flag = False
        hmax = max(h[j-1], hmax)
    if hmax == h[i-1] and flag: ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
keyList = list(range(1,N+1))
values = [True] * N
dic = dict(zip(keyList, values))
HList = list(map(int, input().split()))
ans = []

for i in range(M):
  a, b = map(int, input().split())
  H_a = HList[a-1]
  H_b = HList[b-1]
  if(H_a == H_b):
    dic[a] = False
    dic[b] = False
  elif(H_b > H_a):
    dic[a] = False
  elif(H_a > H_b):
    dic[b] = False


for i in range(1, len(dic.values())+1):
  if(dic[i] == True):
    ans.append(dic[i])
print(len(ans))

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n, m = map(int, input().split())
  h = list(map(int, input().split()))
  ab = [list(map(int, input().split())) for _ in range(m)]
  L = [0] * n

  for i in range(m):
      A =ab[i][0]-1
      B =ab[i][1]-1
      if h[A] == h[B]:
          L[A] -= 1000
          L[B] -= 1000
      else:
          M = max(h[A],h[B])
          if M == h[A]:
              L[A] += 0.33
              L[B] -= 1000
          else: 
              L[B] += 0.33
              L[A] -= 1000
      
  L= list(filter(lambda x: x >= 0, L))
  print(len(L))
  
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ilst = [int(i) for i in input().split()]
tlst = [0]*n
total = 0
for i in range(m):
    List = [int(j) for j in input().split()]
    xlst = []
    for p in List:
        xlst.append(ilst[p-1])
    maxIndex = [i for i, x in enumerate(xlst) if x == max(xlst)]
    if len(maxIndex) >= 2:
        for k in List:
            tlst[k-1] +=1
    else:
        List.pop(maxIndex[0])
        for k in List:
            tlst[k-1] +=1
for x in tlst:
    if x == 0:
        total +=1
print(total)

Submission status: Accepted

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

a = []
kaku = []
for x in range(n[1]) :
    a.append(list(map(int, input().split())))

kaku = [0]* len(m)
cou = 0

for x in range(n[1]):
    if m[a[x][0] -1 ] > m[a[x][1] -1 ]:
        kaku[a[x][0] -1 ] += 1
    else:
        kaku[a[x][0] - 1] -= 100000

    if m[a[x][1] -1 ] > m[a[x][0] -1 ]:
        kaku[a[x][1] -1 ] += 1
    else:
        kaku[a[x][1] - 1] -= 100000

for x in range(len(m)):
    if kaku[x] >= 0 :
        cou += 1

print(cou)

Submission status: Accepted

Solution code:
pre = list(int() for _ in range(300000))

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

for _ in range (M):

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

    st = road[0]
    gl = road[1]

    if H[st-1]<=H[gl-1]:
        pre[st-1] += 1

    if H[st-1]>=H[gl-1]:
        pre[gl-1] += 1

con = 0

for i in range (300000):


    if pre[i] == 0:
        con += 1

ans = 300000 - con

fin = N - ans

print(fin)

Submission status: Accepted

Solution code:
import numpy as np

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

h = input().split()
h = [ int( hi ) for hi in h ]
#print( h )
goodt = [ int( 0 ) ] * n

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

sumg = int( 0 )
for ig in goodt:
    if ig == 0:
        sumg += 1

print( sumg )

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split(' '))

height = np.array(list(map(int, input().split(' '))))
height_all = np.array(list(height))

for i in range(M):
  a, b = map(int, input().split(' '))
  #print(a, b, height[a - 1], height[b - 1])
  if height[a - 1] > height[b - 1]:
    height_all[b - 1] = 0
  
  elif height[a - 1] == height[b - 1]:
    height_all[a - 1] = 0
    height_all[b - 1] = 0
    
  else:
    height_all[a - 1] = 0
    
  #print(height_all)
  
print(len(np.nonzero(height_all)[0]))

Submission status: Accepted

Solution code:
import numpy as np
n,m= list(map(int,input().split()))
h =  list(map(int,input().split()))
l = [[] for i in range(n)]
s = [0 for i in range(n)]
c = [0 for i in range(n)]

for i in range(m):
  r1,r2 = list(map(int,input().split()))
  l[r1-1].append(r2)
  l[r2-1].append(r1)
  s[r1-1]=1
  s[r2-1]=1

for i in range(n):
  if l[i] == []:
    pass
  else:
    for j in range(len(l[i])):
      if h[l[i][j]-1]<h[i]:
        c[i] = 1
      else:
        c[i] = 0
        break

        
print(s.count(0)+c.count(1))

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
H = list(map(int, input().split()))
loadJ = []
kekka = [True] * N
for i in range(M):
    temp = list(map(int, input().split()))
    loadJ.append(temp)
    
    if H[temp[0] - 1] <= H[temp[1] - 1]:
        kekka[temp[0] - 1] = False
    
    if H[temp[1] - 1] <= H[temp[0] - 1]:
        kekka[temp[1] - 1] = False

print(kekka.count(True))

Submission status: Accepted

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

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

cnt = 0
res = {}
for i in range(N):
    res[i] = False
flag = {}
for i in range(N):
    flag[i] = True

for i in d:
    A = i[0]
    B = i[1]
    #print("H[A] > H[B]",H[A],H[B])
    if H[A] > H[B] and flag[A] == True:
        res[A] = True
    else:
        flag[A] = False
        res[A] = False
    #print("H[A] < H[B]",H[A],H[B])
    if H[B] > H[A] and flag[B] == True:
        res[B] = True
    else:
        flag[B] = False
        res[B] = False
print(list(flag.values()).count(True))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())  # x = 1, y = 2
h = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(m)]

# print(n, m, h, ab)

bitl = 2 ** n - 1

for a, b in ab:
    a -= 1
    b -= 1
    if h[a] == h[b]:
        bitl &= ~(1 << a)
        bitl &= ~(1 << b)
        continue
    if h[a] < h[b]:
        bitl &= ~(1 << a)
    else:
        bitl &= ~(1 << b)

print(bin(bitl).count("1"))

Submission status: Accepted

Solution code:
N,M=(int(x) for x in input().split())
T=[1]*N
H=list(map(int,(input().split())))
while 1:
    try:
        A,B=(int(x) for x in input().split())
    except:
        break
    if(H[A-1]<H[B-1]):
        T[A-1]=0
    elif(H[B-1]<H[A-1]):
        T[B-1]=0
    else:
        T[A-1]=0
        T[B-1]=0
print(T.count(1))

Submission status: Accepted

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

class Hill:
  def __init__(self, H):
    self.observatories = [Observatory(i, self) for i in H]
    self.count = 0

  def read_pathway(self, A, B):
    self.observatories[A-1].add_neighbor(B-1)
    self.observatories[B-1].add_neighbor(A-1)
    
  def count_good_observatory(self):
    for observatory in self.observatories:
      observatory.judge()
    print(self.count)

class Observatory:
  def __init__(self,height, Hill):
    self.height = height
    self.neighbors = []
    self.Hill = Hill
    
  def add_neighbor(self, x):
    self.neighbors.append(self.Hill.observatories[x])
    
  def judge(self):
    flag = True
    for neighbor in self.neighbors:
      if self.height <= neighbor.height:
        flag = False
        break      
    if flag:
      self.Hill.count += 1
    
AtCoderHill = Hill(H)
for i in range(M):
  A, B = [int(i) for i in input().split()]
  AtCoderHill.read_pathway(A, B)
AtCoderHill.count_good_observatory()

Submission status: Accepted

Solution code:
import numpy as np

N = input().split()
n= int(N[0])
m = int(N[1])
way = np.zeros(n)
count = 0
h = input().split()
ans = 0
w =0
r = np.zeros(n)

for j in range(m):
    a = input().split()
    b = int(a[0])
    c = int(a[1])
    if int(h[b-1])>int(h[c-1]):
        r[b-1] += 1
        r[c-1] = -1000000
    elif int(h[c-1])>int(h[b-1]):
        r[c-1] += 1
        r[b-1] = -1000000
    else:
        r[b-1] = -1000000
        r[c-1] = -1000000
print(np.count_nonzero(r>=0))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = [int(i) for i in input().split()]
load = [list(map(int, input().split())) for _ in range(m)]
result = {i: 1 for i in range(n)}

for l in load:
    a, b = l[0] - 1, l[1] - 1
    if h[a] < h[b]:
        result[a] = 0
    elif h[a] > h[b]:
        result[b] = 0
    elif h[a] == h[b]:
        result[a] = 0
        result[b] = 0

print(sum(result.values()))

Submission status: Accepted

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

l = []
for i in range(m):
  a, b = [int(j) for j in input().split()]
  if h[a-1] == h[b-1]:
    l.append(a-1)
    l.append(b-1)
  elif h[a-1] < h[b-1]:
    l.append(a-1)
  else:
    l.append(b-1)
    
print(n-len(set(l)))

Submission status: Accepted

Solution code:
import collections
N, M = input().split()
N = int(N)
M = int(M)
H = list(map(int, input().split()))
adjacent = [set() for i in range(N)]
for i in range(M):
  A, B = input().split()
  A = int(A)
  B = int(B)
  adjacent[A-1].add(B-1)
  adjacent[B-1].add(A-1)
Num = 0
for i in range(N):
  num = 1
  for j in adjacent[i]:
    if H[i] <= H[j]:
      num = 0
  if num == 1:
    Num += 1
print(Num)

Submission status: Accepted

Solution code:
import itertools
def rren(): return list(map(int, input().split()))
n,m=rren()
hl=[0] +rren()
al=[tuple(input().split()) for i in range(m)]
ans=[0]+[1]*n
for r in al:
    rl=int(r[0])
    rr=int(r[1])
    if hl[rl] == hl[rr]:
        ans[rr] = 0
        ans[rl] = 0
    elif hl[rl] > hl[rr]:
        ans[rr] = 0
    else:
        ans[rl] = 0
print(sum(ans))

Submission status: Accepted

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

	ans = int(n)
	del_list = set()
	for i in range(m):
		if h[l[i][0]-1] > h[l[i][1]-1] and l[i][1] not in del_list:
			ans -= 1
			del_list.add(l[i][1])
		elif h[l[i][0]-1] < h[l[i][1]-1] and l[i][0] not in del_list:
			ans -= 1
			del_list.add(l[i][0])
		elif h[l[i][0]-1] == h[l[i][1]-1]:
			if l[i][0] not in del_list and l[i][1] not in del_list:
				ans -= 2
				del_list.add(l[i][0])
				del_list.add(l[i][1])
			elif l[i][0] not in del_list:
				ans -= 1
				del_list.add(l[i][0])
			elif l[i][1] not in del_list:
				ans -= 1
				del_list.add(l[i][1])
			else:
				ans += 0
		else:
			ans += 0

	print(ans)





if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split( ))
p=list(map(int,input().split( )))
q=set()
for iddd in range(m):
    i,j=map(int,input().split( ))
    if p[i-1]>p[j-1] :
        q.add(j)
    elif p[j-1]>p[i-1] :
        q.add(i)
    elif p[j-1]==p[i-1]:
        q.add(i)
        q.add(j)
print(n-len(q))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
h2 = [0]*n
a = [0]*m
b = [0]*m
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]:
        h2[a[j]-1] = 1
    elif h[a[j]-1] > h[b[j]-1]:
        h2[b[j]-1] = 1
    else:
        h2[a[j]-1] = 1
        h2[b[j]-1] = 1

print(h2.count(0))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
h_list = list(map(int,input().split()))
roads = []
for i in range(m):
    a,b = map(int,input().split())
    roads.append([a,b])
#print(roads)
terrace = [1] * n
for road in roads:
    if h_list[road[0]-1] > h_list[road[1]-1]:
        terrace[road[1]-1] = 0
    elif h_list[road[0]-1] == h_list[road[1]-1]:
        terrace[road[0]-1] = 0
        terrace[road[1]-1] = 0
    elif h_list[road[0]-1] < h_list[road[1]-1]:
        terrace[road[0]-1] = 0
print(terrace.count(1))

Submission status: Accepted

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

Tallest = [1]*N

for i in range (0,M):
	if H[int(P[i][0])-1] > H[int(P[i][1])-1]:
		Tallest[P[i][1]-1]=0	
	elif H[int(P[i][0])-1] == H[int(P[i][1])-1]:
		Tallest[P[i][0]-1]=0
		Tallest[P[i][1]-1]=0
	else:
		Tallest[P[i][0]-1]=0

print(sum(Tallest))

Submission status: Accepted

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

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

H_peak = list()
for i in range(N):
    H_peak.append(list())

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

good = 0
flag = 1
for i in range(N):
    for j in H_peak[i]:

        if H[i] <= H[j-1]:
            flag = 0
    if flag == 1:

        good += 1
    flag = 1


print(good)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
H=list(map(int, input().split()))
A=[]
B=[]
for i in range(M):
    A1,B1=map(int, input().split())
    A.append(A1)
    B.append(B1)
miti={}
for i in range(M):
    if A[i] in miti:
        miti[A[i]].append(H[B[i]-1])            
    else:
        miti[A[i]]=[]
        miti[A[i]].append(H[B[i]-1])
    if B[i] in miti:
        miti[B[i]].append(H[A[i]-1])            
    else:
        miti[B[i]]=[]
        miti[B[i]].append(H[A[i]-1])
count=0
for i in range(N):
    if i+1 in miti:
        for j in range(len(miti[i+1])):
            if H[i]<=miti[i+1][j]:
                count+=1
                break
print(N-count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ans= 0
rs = []
hs = list(map(int, input().split()))
ds = {}
ok = True
for i in range(m):
    a,b = map(int, input().split())
    if(a in ds):
        ds[a].append(b)
    if(b in ds):
        ds[b].append(a)
    if(a not in ds):
        ds[a] = [b]
    if(b not in ds):
        ds[b] = [a]
for i in range(1, n+1):
    if(i not in ds):
        ans +=1
    else:
        for l in ds[i]:
            if(hs[i-1] <= hs[l-1]):
                ok = False
        if(ok):
            ans +=1
        ok = True
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
h = [int(i) for i in input().split()]
maxTower = [1] * n 

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

print(maxTower.count(1))

Submission status: Accepted

Solution code:
a,b = map(int, input().split())
 
p = [1]*a
ph = list(map(int, input().split()))

 
for i in range(b):
  at,bt = map(int, input().split())
  at-=1
  bt-=1
  if ph[at]>ph[bt]:
    p[bt]=0
  elif ph[at]<ph[bt]:
    p[at]=0
  elif ph[at]==ph[bt]:
    p[at]=0
    p[bt]=0 
 
print(sum(p))

Submission status: Accepted

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

    flg = [True] * n

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

    print(flg.count(True))

main()

Submission status: Accepted

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

    X = [True] * N
    s = set()
    for i in range(M):
        a, b = map(int, input().split())
        s.add(a)
        s.add(b)
        if  H[a - 1] == H[b - 1]:
            X[a - 1] = False
            X[b - 1] = False
        elif H[a - 1] > H[b - 1]:
            X[b - 1] = False
        else:
            X[a - 1] = False


    print(X.count(True))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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


G = [deque([]) for i in range(N+1)] 

road = [input().split() for i in range(M)]

for i in range(M):
    G[int(road[i][0])].append(int(road[i][1]))
    G[int(road[i][1])].append(int(road[i][0]))   
    
count = 0


def dfs(v, num):
    while v:
        tmp = v.pop()
        if hight[tmp - 1] >= hight[num - 1]:
            return False
        else:
            continue
    
    return True

for i in range(N):
    if dfs(G[i+1], i+1):
        count += 1
    else:
        continue

print(count)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
h = list(map(int, input().split()))
tallneigh = [0]*n
G = [[] for i in range(n)]
g = [1 for i in range(n)]

for i in range(m):
    ai, bi = map(int, input().split())
    if h[ai-1] > h[bi-1]:
        g[bi-1] = 0
    elif h[bi-1] >h[ai-1]:
        g[ai-1] = 0
    else:
        g[ai-1] = 0
        g[bi-1] = 0
print(sum(g))

Submission status: Accepted

Solution code:

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

    Res = [ True for i in range(N)]

    for i in range(M):
        v1, v2 = map(int, input().split())
        if H[v1-1] > H[v2-1]:
            Res[v2-1] = False
        elif H[v2-1] > H[v1-1]:
            Res[v1-1] = False
        else:
            Res[v1-1] = False
            Res[v2-1] = False

    count = 0

    for i in range(N):
        if Res[i]:
            count += 1
    
    print(count)


if __name__ == "__main__":
    main()
    pass

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

    cnt = [0]*n
    for j in range(m):
        a, b = ab[j]
        if h[a-1] < h[b-1]:
            cnt[a-1] -= 1
        elif h[b-1] < h[a-1]:
            cnt[b-1] -= 1
        elif h[a-1] == h[b-1]:
            cnt[a-1] -= 1
            cnt[b-1] -= 1

    
    return cnt.count(0)




print(solve())

Submission status: Accepted

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

Submission status: Accepted

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

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

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

for i in range(M):
    AB = list(map(int, input().split()))
    N_addj[AB[0]-1].append(AB[1]-1)
    N_addj[AB[1]-1].append(AB[0]-1)


N_memo = [0] * N

num = 0


arr = []


for i in range(N):
    flag = True
    for j in N_addj[i]:
        if(H[i] <= H[j]):
            flag = False
            break
    if(flag):
        num = num + 1

print(num)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = list(map(int, input().split()))
is_tower_good = [1]*n
for j in range(m):
    bridge = list(map(int, input().split()))
    if h[bridge[0] - 1] > h[bridge[1] - 1]:
        is_tower_good[bridge[1] - 1] = 0
    elif h[bridge[0] - 1] < h[bridge[1] - 1]:
        is_tower_good[bridge[0] - 1] = 0
    else:
        is_tower_good[bridge[1] - 1] = 0
        is_tower_good[bridge[0] - 1] = 0


print(is_tower_good.count(1))

Submission status: Accepted

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

for q in Q:
  if H[q[0] -1] > H[q[1] -1]:
    H_[q[1]-1] = True
  elif H[q[0] -1] < H[q[1] -1]:
    H_[q[0]-1] = True
  else:
    H_[q[1]-1] = True
    H_[q[0]-1] = True
    
print(N - sum(H_))

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
l=list(f())
t=[1]*n
for _ in range(m):
  a,b=f()
  if l[a-1]<=l[b-1]: t[a-1]=0
  if l[b-1]<=l[a-1]: t[b-1]=0
print(sum(t))

Submission status: Accepted

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


dictionary = {}
for A, B in AB:
    if dictionary.get(A) is None:
        dictionary[A] = []
    if dictionary.get(B) is None:
        dictionary[B] = []

    dictionary[A].append(H[B - 1])
    dictionary[B].append(H[A - 1])
# print(dictionary)

count = 0
for i, heights in dictionary.items():
    # print(i, type(i), H[i - 1], heights)
    if H[i - 1] > max(heights):
        count += 1

import itertools

# paths = list(itertools.chain.from_iterable(AB))
# print(paths)
for i in range(1, N + 1):
    if dictionary.get(i) is None:
        count += 1

print(count)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
hlist = list(map(int,input().split()))
ten = []
append = ten.append
for i in range(n):
    append(1)
#print(ten)
for i in range(m):
    a,b = map(int,input().split())
    if hlist[a-1] > hlist[b-1]:
        ten[b-1] = 0
    elif hlist[b-1] > hlist[a-1]:
        ten[a-1] = 0
    elif hlist[b-1] == hlist[a-1]:
        ten[a-1] = 0
        ten[b-1] = 0


print(sum(ten))

Submission status: Accepted

Solution code:
def main():
  nm = list(map(int,input().split()))
  h = list(map(int,input().split()))
  hairetu = [0]*(nm[0]+1)
  #print(hairetu)
  for m in range(0,nm[1],1):
    ab = list(map(int,input().split()))
    if(h[ab[0]-1]>h[ab[1]-1]):
      #print(ab[1])
      hairetu[ab[1]] = -1
    elif(h[ab[0]-1]==h[ab[1]-1]): 
      hairetu[ab[1]] = -1
      hairetu[ab[0]] = -1
    else:hairetu[ab[0]] = -1
  sum = 0
  for x in range(1,nm[0]+1,1):
    if(hairetu[x]==0):sum = sum + 1
  
  #print(hairetu)
  print(sum)
  
main()

Submission status: Accepted

Solution code:
import sys;
s = input().split();
n = int(s[0]);
m = int(s[1]);
h = list(map(int,input().split()));
c = [];
cnt = 0;
for i in range(n):
    c.append(True);
for i in range(m):
    tmp = input().split();
    n1 = int(tmp[0]);
    n2 = int(tmp[1]);
    if(h[n1 - 1] <= h[n2 - 1]):
        c[n1 - 1] = False;
    if(h[n1 - 1] >= h[n2 - 1]):
        c[n2 - 1] = False;

for i in range(n):
    if(c[i] == True):
        cnt += 1;


print(cnt);

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for m in range(M)]
AB = list(map(list, set(map(tuple, AB))))

i = []
for m in range(len(AB)):
    a = AB[m][0]
    b = AB[m][1]
    if H[a-1] > H[b-1]:
        i.append(b-1)
    elif H[a-1] < H[b-1]:
        i.append(a-1)
    else:
        i.append(a-1)
        i.append(b-1)

i = list(set(i))
print(len(H)-len(i))

Submission status: Accepted

Solution code:
N , M = map(int,input().split())
h = list(map(int, input().split()))
graph = [[] for _ in range(N)]
for _ in range(M):
    a , b = map(int,input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
ans=0
 
for index,i in enumerate(graph):
    judge=1
    for j in i:
        if h[index] <= h[j]:
            judge=0
            break
    if judge==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:


def main():
    N, M = list(map(int, input().split(' ')))
    
    Hn = list(map(int, input().split(' ')))
    
    ABn = []
    for _ in range(M):
        ABn.append(list(map(int, input().split(' '))))
    
    dic_path = {i+1:[] for i in range(len(Hn))}
    
    for i in range(M):
        a = ABn[i][0]
        b = ABn[i][1]
        
        dic_path[a].append([a, b])
        dic_path[b].append([b, a])
    
    # print(dic_path)
    
    result = 0
    for i, paths in dic_path.items():
        # print('---------', i)
        # print(i, paths)
        
        # continue
        if len(paths) == 0:
            # print('i:', i)
            result += 1
            continue
        # continue
        flag = True
        for path in paths:

            a = path[0]
            b = path[1]
            ha = Hn[a-1]
            hb = Hn[b-1]
            # print('a, b, ha, hb:', a, b, ha, hb)
            if hb >= ha:
                flag = False
                # print('a, b, ha, hb:', a, b, ha, hb)
                break

        if flag is True:
            # print('i:',i)
            result += 1
    print(result)




main()