이번 문제는 플로이드-와샬을 통해 해결하였다. 기존의 플로이드-와샬 문제와 조금 다르게 초기의 최소 비용 리스트를 최댓값이 아닌 0으로 모두 채워줘야 한다. 그리고 a가 b보다 작다고 할 때에, 최소 비용 리스트[a][b]를 1로 갱신해준다. 이렇게 초기화가 되면, 플로이드-와샬 알고리즘을 통해 최소 비용을 갱신해준다. 최소 비용 리스트[i][j]가 1이거나, 최소 비용 리스트[i][k]가 1이고 최소 비용리스트[k][j]가 1인 경우, 최소 비용 리스트[i][j]를 1로 갱신해준다. 이 과정을 거치고 나면 [i][:]에는 i보다 작은 학생이 1로 표시되어 있고, [:][i]에는 i보다 큰 학생이 1로 표시되어 있다. [i][:]와 [:][i]의 합이 n-1과 같다면 i를 기준으로 i보다 작은 학생과 큰 학생을 모두 알 수 있으므로 i의 등수를 알 수 있게 된다.

• n, m을 입력받는다.
• 최소 비용을 저장할 리스트 dist를 (n+1)*(n+1)의 크기로 선언하고 0으로 채운다.
• m번 반복하는 for문을 돌린다.
  -> a, b를 입력받는다.
  -> dist[a][b]를 1로 갱신한다.
• 1부터 n까지 반복하는 k에 대한 for문을 돌린다.
  -> 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  --> 1부터 n까지 반복하는 j에 대한 for문을 돌린다.
  ---> 만약 dist[i][j]가 1이거나, dist[i][k]와 dist[k][j]가 모두 1일 경우, dist[i][j]를 1로 갱신한다.
• 정답을 저장하는 변수 answer를 0으로 선언한다.
• 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> i보다 크거나 작은 학생의 수를 저장할 임시 변수 result를 0으로 선언한다.
  -> 1부터 n까지 반복하는 j에 대한 for문을 돌린다.
  --> result에 dist[i][j]+dist[j][i]의 값을 더한다.
  -> 만약 result가 n-1과 같을 경우,
  --> answer를 1 증가시킨다.
• answer를 출력한다.

Code

import sys
input=sys.stdin.readline
n, m=map(int, input().split())
dist=[[0]*(n+1) for _ in  range(n+1)]
for _ in range(m):
    a, b=map(int, input().split())
    dist[a][b]=1
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if dist[i][j]==1 or (dist[i][k]==1 and dist[k][j]==1):
                dist[i][j]=1
answer=0
for i in range(1, n+1):
    result=0
    for j in range(1, n+1):
        result+=dist[i][j]+dist[j][i]
    if result==n-1:
        answer+=1
print(answer)