1613번: 역사

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


$O(n^3)$

x가 y보다 먼저 일어났다면 x->y 간선을 생성한다.
x와 y사이 x->t->y와 같이 t를 경유할 수 있다면 x->y를 만든다.
이는 플로이드 알고리즘으로 $O(n^3)$ 시간에 가능하다.

#include<cstdio>
int n, k, s, c[401][401], x, y;
int main() {
    scanf("%d%d", &n, &k);
    while (k--) scanf("%d%d", &x, &y), c[x][y] = 1;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) c[j][k] |= c[j][i] & c[i][k];
    scanf("%d", &s);
    while (s--) scanf("%d%d", &x, &y), printf("%d\n", c[y][x] - c[x][y]);
    return 0;
}