백준 1613: 역사

역사 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

12216

4299

3068

34.682%

문제

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.

세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.

입력

첫째 줄에 첫 줄에 사건의 개수 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
• 문제의 오타를 찾은 사람: joonas

알고리즘 분류

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

메모

 

#include<iostream>
using namespace std;

bool arr[401][401];
int n, k;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n >> k;
	int from, to;
	for (int i = 1; i <= k; i++) {
		cin >> from >> to;
		arr[from][to] = true;
	}

	for (int br = 1; br <= n; br++) 
		for (int i = 1; i <= n; i++) 
			for (int j = 1; j <= n; j++) 
				if (arr[i][br] && arr[br][j])
					arr[i][j] = true;

	int t;
	cin >> t;
	
	for (int i = 0; i < t; i++) {
		cin >> from >> to;
		if (arr[from][to] == false && arr[to][from] == false) {
			cout << 0 << '\n';
		}
		else if (arr[from][to] == false && arr[to][from] == true) {
			cout << 1 << '\n';
		}
		else if (arr[from][to] == true && arr[to][from] == false) {
			cout << -1 << '\n';
		}
	}


	return 0; 
}