역사

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	13395	4248	3117	34.196%

문제

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다.

즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.

세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까?

이를 해결하는 프로그램을 작성해 보도록 하자.

입력

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다.

다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다.

이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다.

물론 사건의 전후 관계가 모순인 경우는 없다.

다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다.

다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다.

사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

s줄에 걸쳐 물음에 답한다.

각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1,

뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.

예제 입력 1

5 5
1 2
1 3
2 3
3 4
2 4
3
1 5
2 4
3 1

예제 출력 1

0
-1
1

출처

• 문제를 만든 사람: author5
• 데이터를 추가한 사람: djs100201
• 문제의 오타를 찾은 사람: joonas

알고리즘 분류

• 그래프 이론
• 플로이드–워셜

---

접근 방법

통과된 코드

#include <iostream>
#include <vector>
#include <list>

using namespace std;

int n, k, f, b, s;

constexpr int MAX = 401;

vector<pair<int, int>> graph[MAX];

list<pair<int, int>> myList;

int disArr[MAX][MAX];

int main()
{
	ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
	// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> k;

	// 사건의 전후 관계 입력
	for (int i = 0; i < k; i++) {
		cin >> f >> b;
		graph[f].push_back(make_pair(b, -1));
		graph[b].push_back(make_pair(f, 1)); // 역방향 가능
	}

	// 질문을 입력 받는다.
	cin >> s;

	pair<int, int> tempP;

	while (s--) { // 문제를 입력받는다.
		cin >> tempP.first >> tempP.second;
		myList.push_back(tempP);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < graph[i].size(); j++) {
			int v = graph[i][j].first;
			int weight = graph[i][j].second;
			disArr[i][v] = weight;
		}
	}


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

	for (auto it = myList.begin(); it != myList.end(); it++) {
		cout << disArr[it->first][it->second] << "\n";

	}

	return 0;
}