BOJ : 1613 역사

---

[BOJ 1613(G3)리뷰]

플로이드-와셜을 이용한 알고리즘이다.
보통 모든 노드간의 최단거리를 구하는데 사용되지만 이러한 문제에도 응용할 수 있다.

결국 각각의 노드는 모든 노드에 대해 자신과 연결된 노드를 이용하여 노드간의 관계를 정의할 수 있냐 없냐로 나뉜다.
그리하여, 플로이드-와셜 알고리즘을 통하여 모든 연결을 확인하여 연결이 가능한 경우에만 배열에 기록하면 된다.

예를들어, "1 2"라는 입력은 1번사건이 2번사건보다 먼저 일어났다는 의미이다. 이후에 "2 3"이라는 입력이 있다면
1->2->3의 관계를 통해 1번사건이 3번사건보다 먼저 일어났다는것을 알 수 있다.

이렇게 알고리즘을 적용하고나면 연결여부를 기록한 배열에는 각각의 노드마다 자신보다 뒤에 일어난 사건의 번호들의 index를 가지게 된다.

만약 dist[1][2]값과 dist[2][1]값이 모두 0이라면 이는 두 사건간의 관계를 유추할 수 없다는 의미를 갖게된다.
하지만, dist[1][2]가 1이라면 1번이 2번사건보다 먼저, dist[2][1]이 1이라면 2번사건이 1번보다 먼저 일어났음을 의미한다.

위 조건들을 생각하여 구현하면 된다.

/*
	21.01.22
	BOJ : 1613 역사 (https://www.acmicpc.net/problem/1613)
	플로이드-워셜 알고리즘
*/
#include <bits/stdc++.h>
using namespace std;

int adj[401][401];
int n, k, s;

void floyd(int (*dist)[401]) {

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

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

	cin >> n >> k;

	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b;

		adj[a][b] = 1;
	}

	floyd(adj);

	cin >> s;

	while (s--) {
		int a, b;
		cin >> a >> b;

		if (adj[a][b] == 0 && adj[b][a] == 0) {
			cout << 0;
		}
		else if (adj[a][b]) {
			cout << -1;
		}
		else if (adj[b][a]) {
			cout << 1;
		}

		cout << '\n';
	}

	return 0;
}