백준 1613 c++ "역사" -[PlusUltraCode]

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

1613번: 역사

 

[필자 사고]

플로이드 와샬 알고리즘을 이용하면 쉽게 해결할 수 있는 문제이다.

 

입력창을 보면 선후 관계 화살표로 주어 졌으므로 와샬 알고리즘을 사용후에는 후속 조취가 필요하다.

 

그 이유는 다음과 같다.

 

1->4 의 값이 자연수이고 4->1의 값이 무한대일때 1과4는 선후관계가 형성 되었따. 

 

1->4를 보면 선후관계를 알 수 있지만 4->1을 보면 선후관계를 판별할 수 없기 때문이다.

 

이 부분만 알고 있으면 문제를 쉽게 해결할 수 있다.

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> Arr;
int N, M;
int T;
const int INF = 987654321;

void Input() {
	cin >> N >> M;
	Arr.resize(N + 1);
	for (int i = 0; i <= N; i++) {
		Arr[i].resize(N + 1, INF);
	}
	for (int i = 0; i < M; i++) {
		int s, e;
		cin >> s >> e;
		Arr[s][e] = 1;
	}
	
}

void Floyd_Warshall() {
	for (int k = 1; k <= N; k++) {
		for (int s = 1; s <= N; s++) {
			for (int e = 1; e <= N; e++) {
				Arr[s][e] = min(Arr[s][e], Arr[s][k] + Arr[k][e]);
			}
		}
	}
	for (int s = 1; s <= N; s++) {
		for (int e = 1; e <= N; e++) {
			if (Arr[s][e] >= 1 && Arr[s][e] < INF) {
				Arr[e][s] = -1;
			}
		}
	}
}



int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	Floyd_Warshall();
	
	cin >> T;
	for (int i = 0; i < T; i++) {
		int s, e;
		cin >> s >> e;
		if (Arr[s][e] == INF) {
			cout << 0;
		}
		else if (Arr[s][e] != -1) {
			cout << -1;
		}
		else cout << 1;
		cout << '\n';
	}
}