문제
사건의 전후 관계 K개가 주어질 때, 주어진 사건 쌍의 순서를 판별하라.
입력
첫째 줄에 N(사건 수), K(관계 수), 이후 K줄에 "a b"(a가 b보다 먼저), 그 다음 S줄에 질의 쌍이 주어진다.
출력
각 질의에 대해 앞이면 -1, 뒤면 1, 판별 불가면 0을 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 5 1 2 1 3 2 3 3 4 2 4 3 1 5 2 4 3 1 | 0 -1 1 |
풀이
플로이드-워셜로 전이적 폐쇄를 구하여 도달 가능성으로 순서를 판별한다.
- 전후 관계를 boolean 인접 행렬에 기록한다
- 플로이드-워셜로 간접 관계까지 전파한다 (j→i 이고 i→k이면 j→k)
- 질의 (s, e)에 대해 map[s][e]이면 -1, map[e][s]이면 1, 둘 다 아니면 0
핵심 아이디어: 전이적 폐쇄로 모든 간접 관계를 미리 구하면 각 질의를 O(1)에 응답할 수 있다.
코드
package day699;
public class Day672BOJ1613역사 {
static int N, K, S;
static boolean[][] map;
public static void main(String[] args) throws Exception {
N = read();
K = read();
map = new boolean[N + 1][N + 1];
for (int i = 0; i < K; i++) {
int a = read();
int b = read();
map[a][b] = true;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
for (int k = 1; k <= N; k++) {
if (map[j][i] && map[i][k])
map[j][k] = true;
}
}
}
S = read();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < S; i++) {
int s = read();
int e = read();
int ans = 0;
if (map[s][e])
ans = -1;
if (map[e][s])
ans = 1;
sb.append(ans).append("\n");
}
System.out.println(sb);
}
static int read() throws Exception {
int c, n = System.in.read() & 15;
while ((c = System.in.read()) > 32) {
n = (n << 3) + (n << 1) + (c & 15);
}
return n;
}
}복잡도
- 시간: O(V³)
- 공간: O(V²)