우물 안 개구리

문제

# N : 회원 수, M : 친분 관계 수
N, M = map(int, input().split())

# 회원별 역기의 무게
W = list(map(int, input().split()))

# 회원별 친분 관계도
F = [[] for i in range(N+1)]

# 친분 관계 등록
for i in range(M):
    x, y = map(int, input().split())
    F[x].append(y)
    F[y].append(x)

# dp를 위한 리스트
best = [True for i in range(N+1)]

for n in range(1, N+1):
    # True인 회원만 확인
    if best[n]:
        w = W[n-1]
        # 친분 관계인 회원 확인
        for m in F[n]:
            # 다른 회원의 무게와 크거나 같으면
            if w <= W[m-1]:
                best[n] = False

# 0번째 제외
print(best.count(True)-1)

문제를 읽고 처음에는 dfs를 생각했다.
하지만 친분 관계에 있는 회원만 확인해야 하므로 dfs로 하면 틀린다.
a와 b, b와 c가 친분 관계에 있다고 a와 c가 친분 관계에 있지 않기 때문이다.