역사

*플로이드 와샬 알고리즘과 위상정렬 사용 

*플로이드 와샬 알고리즘으로 일단 두 정점의 선후관계가 있는지 파악한다. 

*선후관계가 없으면 0

*선후관계가 있는데 그 순서가 명확하지 않을 때는 위상정렬을 사용해서 비교한다. (위상정렬의 값이 더 큰 순서가 후이다.)

 

#include <iostream> #include <vector> #include <algorithm> #define INF 987654321 using namespace std; int dp[401][401]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = i == j ? 0 : INF; } } int indegree[401] = { 0 }; for (int i = 0; i < k; i++) { int a, b; cin >> a >> b; dp[a][b] = 1; indegree[b]++; } for (int a = 1; a <= n; a++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (a == i || a == j || i == j) continue; dp[i][j] = min(dp[i][j], dp[i][a] + dp[a][j]); } } } int s; cin >> s; for (int i = 0; i < s; i++) { int a, b; cin >> a >> b; if (dp[a][b] == INF) { if (dp[b][a] == INF) cout << 0 << '\n'; else cout << 1 << '\n'; } else { if (dp[b][a] == INF) cout << -1 << '\n'; else { if (indegree[a] < indegree[b]) cout << -1 << '\n'; else cout << 1 << '\n'; } } } return 0; }