[백준/BOJ] 백준 1613번 : 역사

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

1613번: 역사

 

사건 사이의 관계 그래프를 2차원 배열로 표시하여, 플로이드 와샬을 통해 각 지점에서 도달할 수 있는 지점을 체크해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, k;
int adj[405][405];
int s;
vector<int> result;

void pre() {
	for (int i = 0; i < 405; i++) {
		adj[i][i] = 1;
	}
}

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

	pre();

	cin >> n >> k;

	for (int i = 0; i < k; i++) {
		int u, v;
		cin >> u >> v;

		adj[u][v] = 1;
	}

	//도달할 수 있는 위치를 플로이드 와샬을 통해 구한다
	for (int k = 0; k < 405; k++) {
		for (int i = 0; i < 405; i++) {
			for (int j = 0; j < 405; j++) {
				adj[i][j] |= (adj[i][k] & adj[k][j]);
			}
		}
	}

	cin >> s;

	for (int i = 0; i < s; i++) {
		int u, v;
		cin >> u >> v;

		//u에서 v로 도달할 수 있을때
		if (adj[u][v] == 1) {
			result.push_back(-1);
		}

		//v에서 u로 도달할 수 있을때
		else if (adj[v][u] == 1) {
			result.push_back(1);
		}

		else {
			result.push_back(0);
		}
	}

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << "\n";
	}

	return 0;
}