문제

결국 4번 학생이 3등이라는 정보만 알 수 있음 → 답 출력: 1

입력예시

6 6

1 5

3 4

4 2

4 6

5 2

5 4

출력예시

1

문제 풀이 아이디어

1. 플로이드 워셜 알고리즘 사용
   1. 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우
2. 모든 노드에 대해서 다른 노드로 도달이 가능한지 여부를 확인해야 함
   1. 도달 가능 = 성적 비교 가능
   2. if graph[i][j] == graph[j][i] == INF → 순위 알 수 없음.
3. 자기보다 성적이 낮은 학생 수 + 자기보다 성적이 높은 학생 수 = 총 학생 수 → 순위 알 수 있음

코드

n, m = map(int, input().split()) # 학생들의 수 n, 두 학생의 성적을 비교한 횟수 m
INF = int(1e9)
graph = [[INF] * (n + 1) for _ in range(n + 1)] # 모든 간선을 무한으로 초기화
    
for a in range(1, n + 1) : # 자기 자신으로 향하는 건 0으로 초기화
    for b in range(1, n + 1) :
        if a == b :
            graph[a][b] = 0

for _ in range(m): # i 성적 < j 성적
    i, j = map(int, input().split())
    graph[i][j] = 1
            
# 플로이드 와샬 알고리즘
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
            
ans = 0 # 출력할 결과
for i in range(1, n + 1):
    ct = 0 # 비교할 결과
    for j in range(1, n + 1):
        if graph[i][j] != INF or graph[j][i] != INF: # 성적 비교가 가능하다면
            ct += 1
    if ct == n: # 총 비교할 수 있는 수 == 총 학생 수
        ans += 1
            
print(ans)