(백준/Python) 1613 연혁

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
accident = ((0) * n for _ in range(n))
for _ in range(k):
    a, b = map(int, input().split())
    # 늦게 일어난 사건을 1로 표시
    accident(a-1)(b-1) = 1

# i -> k 가 늦게 일어났고, k -> j도 늦게 일어났다면
# i -> j도 후순위인 것
for k in range(n):
    for i in range(n):
        for j in range(n):
            if accident(i)(k) == 1 and accident(k)(j) == 1:
                accident(i)(j) = 1
            
            if i == j:
                accident(i)(j) = 0
# 일어난 일 유추하기
s = int(input())
for _ in range(s):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if accident(a)(b):
        print("-1")
    elif accident(b)(a):
        print("1")
    else:
        print("0")

해결하는 과정

유체 – 워샬

1. 늦은 이벤트를 1로 표시

2. (i)(k)가 1이고 (k)(j)가 1이면 (i)(j)도 1입니다.

3. (a)(b)가 1이면 b는 종속입니다.

반대로 (b)(a)가 1이면 a는 다음에 종속됩니다.