역사

백준 1613번: 역사

아이디어

플로이드 한 번 돌리고 a->b만 INF면 b가 먼저 일어난거고, b->a만 INF면 a가 먼저 일어난거고, 둘 다 INF면 그래프가 연결되어 있지 않아서 전후 관계를 알 수 없다.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int INF = 1e9, MAX = 401;
int N, M, S;
int graph[MAX][MAX];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        graph[a-1][b-1] = 1;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (!graph[i][j]) graph[i][j] = INF;
        }
    }

    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]);
            }
        }
    }

    cin >> S;
    for (int i = 0; i < S; i++) {
        int a, b;
        cin >> a >> b;
        if (graph[a-1][b-1] == INF && graph[b-1][a-1] == INF) cout << 0 << '\n';
        else if (graph[a-1][b-1] == INF && graph[b-1][a-1] != INF) cout << 1 << '\n';
        else cout << -1 << '\n';
    }

    return 0;
}

여담

한국사 세계사 시간 특) 꿀잠시간