BOJ 1613 역사

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

1613번: 역사

 

딱 보면 위상정렬로 착각하기 쉬운 문제입니다. 위상정렬보다는 훨씬 쉬운 방법으로 풀립니다.

 

위상정렬을 하듯이 생각해보면, 어떠한 사건 $a$가 사건 $b$보다 먼저 일어났다는 것은, $a$에서 $b$로 가는 단방향 간선이 존재한다고도 생각할 수 있습니다. 모순되는 사건이 존재하지 않는다고 했으므로, 그렇게 구성된 그래프는 항상 DAG의 형태를 띄게 됩니다. 그래프를 구성한 후 해당 그래프에서 사건 $u$에서 사건 $v$로 가는 path가 있을 경우 $u$가 $v$보다 먼저 일어났다는 뜻이고, 반대로 $v$에서 $u$로 가는 path가 있을 경우 $v$가 $u$보다 먼저 일어났다는 뜻입니다. 두 정점을 잇는 간선이 없을 경우는 정보가 충분하지 않다는 뜻이고요.

 

제한을 보면 정점의 수가 최대 400개이므로 플로이드 워셜 알고리즘을 이용하면 쉽게 풀 수 있습니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>

#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '

const int INF = 0x3f3f3f3f;

using namespace std;

int T, n, k, graph[440][440];

int32_t main(void) {
    FastIO;

#ifdef HN
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    T = 1;
    //cin >> T;

    while (T--) {
        cin >> n >> k;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                graph[i][j] = INF;
            }
        }

        for (int i = 0; i < k; i++) {
            int a, b;
            cin >> a >> b;
            graph[a][b] = 1;
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (graph[i][j] > graph[i][k] + graph[k][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }

        int s;
        cin >> s;
        while (s--) {
            int a, b;
            cin >> a >> b;
            if (graph[a][b] < INF) cout << -1 << endl;
            else if (graph[b][a] < INF) cout << 1 << endl;
            else cout << 0 << endl;
        }
    }

    return 0;
}