백준 2458 키 순서 (파이썬)

https://www.acmicpc.net/problem/2458

2458번: 키 순서

1. 플로이드-와샬로 이동 가능한 경로를 모두 구한다

2. i에서 j로 이동할 수 있으면 cnt의 i번째와 j번째 값을 증가시킨다

3. cnt에서 값이 n-1인 경우의 수를 출력

import sys

INF = sys.maxsize
n, m = map(int, input().split())
a = [[INF]*n for _ in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    a[x-1][y-1] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            if a[i][k] + a[k][j] == 2:
                a[i][j] = 1

cnt = [0]*n
for i in range(n):
    for j in range(n):
        if a[i][j] == 1:
            cnt[i] += 1
            cnt[j] += 1
print(cnt.count(n-1))