1. 문제 설명

키 순서

2. 문제 분석

플로이드-워셜 알고리즘을 통해 i와 j번 노드 간의 거리를 구할 수 있다. 이때 i번에서 j번까지, 그리고 j번에서 i번까지 거리가 무한대라면 우열을 매길 수 없다.

3. 나의 풀이

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
INF = sys.maxsize
nodes = [[INF for _ in range(n+1)] for _ in range(n+1)]
for i in range(n+1): nodes[i][i] = 0

for _ in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    nodes[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 nodes[i][j] > nodes[i][k] + nodes[k][j]:
                nodes[i][j] = nodes[i][k] + nodes[k][j]

cnt = 0
for i in range(1, n+1):
    is_rankable = True
    for j in range(1, n+1):
        if nodes[i][j] == INF and nodes[j][i] == INF:
            # i로부터의 거리 또는 i에 대한 거리가 모두 측정 불가할 때에는 등수를 매길 수 없다.
            is_rankable = False
            break
    if is_rankable: cnt += 1

print(cnt)