BOJ 1613 역사

역사 [골드 3]

---

문제 링크

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

풀이

사건의 앞뒤 관계를 order에 저장 후 전후 관계를 알 수 없는 order[x][y] == 0에 대해 임의의 k를 통해 order[x][k], order[k][y]가 정의된 경우, 이를 바탕으로 order[x][y]를 정의한다.

#include <iostream>
#include <vector>

#define MAX 401

using namespace std;

int N, K, S;
int order[MAX][MAX];
vector<pair<int, int>> query;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> K;

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

    for (int k = 1; k <= N; k++)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (order[i][j] == 0)
                {
                    if (order[i][k] == 1 && order[k][j] == 1)
                    {
                        order[i][j] = 1;
                    }
                    else if (order[i][k] == -1 && order[k][j] == -1)
                    {
                        order[i][j] = -1;
                    }
                }
            }
        }
    }

    cin >> S;

    int a, b;
    for (int i = 0; i < S; i++)
    {
        cin >> a >> b;
        cout << order[a][b] << "\n";
    }

    return 0;
}