[백준/BOJ/1613] 역사

Topology sort 인 줄 알았으나 Floyd 를 사용후에 하나의 정점에서 다른 정점으로 갈 수 있는지 없는지 여부만 파악

 

#include <iostream>
using namespace std;
const int MAX = 405;
int N, K, dp[MAX][MAX];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> K;
	for (int i = 0; i < K; i++) {
		int u, v; cin >> u >> v;
		dp[u][v] = 1;
	}
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (dp[i][k] && dp[k][j]) dp[i][j] = 1;
			}
		}
	}
	int m; cin >> m;
	for (int i = 0; i < m; i++) {
		int u, v; cin >> u >> v;
		if (dp[u][v] == 1 && dp[v][u] == 0) cout << "-1\n";
		else if (dp[u][v] == 0 && dp[v][u] == 1) cout << "1\n";
		else cout << "0\n";
	}
	return 0;
}