[1613] 역사

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

1613번: 역사

사이클이 없는 단방향 그래프이므로, i에서 j로 갈 수 있다면 i가 j보다 먼저 일어난 사건이다.

간선의 가중치를 1로잡고 연결해서, 플로이드를 돌리면 쿼리당 O(1)에 가능하다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n, m, dst[405][405];

constexpr int INF = 12345678;

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m;

    int i, j, k;

    for (i = 1; i <= n; i++)

        for (j = 1; j <= n; j++) dst[i][j] = INF;

    for (i = 0; i < m; i++) {

        int A, B;

        cin >> A >> B;

        dst[A][B] = 1;

    }

    for (i = 1; i <= n; i++) dst[i][i] = 0;

    for (k = 1; k <= n; k++)

        for (i = 1; i <= n; i++)

            for (j = 1; j <= n; j++)

                dst[i][j] = min(dst[i][k] + dst[k][j], dst[i][j]);

    int t;

    cin >> t;

    while (t--) {

        int A, B;

        cin >> A >> B;

        if (dst[A][B] == INF && dst[B][A] == INF)

            cout << 0;

        else if (dst[A][B] < INF)

            cout << -1;

        else

            cout << 1;

        cout << '\n';

    }

    return 0;

}

---