백준 1613 역사 (파이썬)

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

1613번: 역사

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

2. 앞에 있는 사건이 먼저 일어난 경우가 있는지 우선 체크해본다

3. 먼저 일어나지 않았다면 다른 케이스를 검증하여 조건에 맞게 값을 출력한다

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
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

s = int(input())
for _ in range(s):
    x, y = map(int, input().split())
    if a[x-1][y-1] == 1:
        print(-1)
    elif a[y-1][x-1] == 1:
        print(1)
    elif a[x-1][y-1] == 0:
        print(0)