백준 알고리즘 2458번 키 순서(python)

기본적인 플로이드-와샬 문제이다. PyPy3로 제출해야 통과된다.

(특정 노드가 다른 노드를 가리키는 횟수 + 다른 노드가 특정 노드를 가리키는 횟수) == N-1이라면

그 특정 노드의 순서를 알 수 있다는 점이 핵심이다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[0]*N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1][b-1] = 1
for k in range(N):
    for a in range(N):
        for b in range(N):
            if graph[a][k] == 1 and graph[k][b] == 1:
                graph[a][b] = 1
res = 0
for i in range(N):
    t = 0
    for j in range(N):
        t += graph[i][j] + graph[j][i]
    if t == N-1:
        res += 1
print(res)