백준 1613번 역사 C++

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

1613번: 역사

 

플로이드-워셜을 통해 전체 사건의 순서에 대한 정보를 2차원 벡터에 저장해서 풀었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, k;
vector<vector<int>> graph;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> k;
    graph = vector<vector<int>>(n + 1, vector<int>(n + 1, -1));
    for (int i = 0; i < k; i++) {
        int s, e;
        cin >> s >> e;
        graph[s][e] = 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][K] == -1) continue;
                if (graph[K][j] == -1) continue;
                graph[i][j] = 1;
            }
        }
    }
    int s;
    cin >> s;
    for (int i = 0; i < s; i++) {
        int a, b;
        cin >> a >> b;
        int ans;
        if (graph[a][b] == 1) ans = -1;
        else if (graph[b][a] == 1) ans = 1;
        else ans = 0;
        cout << ans << "\n";
    }
}