백준 10159 저울 (파이썬)

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

10159번: 저울

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

2. i에서 j로 갈 수 없고 j에서 i로 갈 수 없으면 무게를 비교할 수 없으므로 cnt를 증가

3. 자기자신을 비교한 경우를 제외하기 위해 cnt-1을 출력

import sys

INF = sys.maxsize
input = sys.stdin.readline

n, m = int(input()), int(input())
a = [[0]*n for _ in range(n)]

for _ 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] and a[k][j]:
                a[i][j] = 1

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