앞선 사건을 from, 뒤의 사건을 to라 했을 때 단방향이므로 arr[from][to] = 1로 저장하기 (1 아니어도 상관없음. 사건이 일어났다는 표시만 하면 됨.)
플로이드 와샬 알고리즘으로 최단 거리를 구한 후
1) arr[from][to] > 0 && arr[from][to] != INF : 자연수. from이 to보다 앞에 일어났음
2) arr[from][to] >0 && arr[from][to] == INF : 무한대. 어떤 사건이 앞인지 모름
3) arr[from][to] == INF && arr[to][from] >0 : to가 from보다 앞에 일어남
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include<cstdio>
#define INF 1000000000
int arr[402][402];
int n,k,s,from,to;
int main(void){
scanf("%d %d", &n, &k);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++)
arr[i][j]= (i==j)?0:INF;
}
for(int i=0; i<k; i++){
scanf("%d %d", &from, &to);
arr[from][to]=1;
}
for(int k=1; k<=n; k++){
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(arr[i][j]>arr[i][k]+arr[k][j])
arr[i][j]=arr[i][k]+arr[k][j];
}
}
}
scanf("%d", &s);
for(int i=0; i<s; i++){
scanf("%d %d", &from, &to);
if(arr[from][to]!=INF && arr[to][from]==INF) printf("-1\n");
else if(arr[from][to]== INF && arr[to][from]!=INF) printf("1\n");
else printf("0\n");
}
return 0;
}
|
cs |
- Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main{
static int maxNum = 987654321;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
int[][] arr = new int[n+1][n+1];
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++)
arr[i][j] = maxNum;
}
int from=0, to=0;
for(int i=0; i<t; i++){
st = new StringTokenizer(br.readLine(), " ");
from = Integer.parseInt(st.nextToken());
to = Integer.parseInt(st.nextToken());
arr[from][to] = 1;
}
for(int k=1; k<=n; k++){
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
arr[i][j] = Math.min(arr[i][j], arr[i][k]+arr[k][j]);
}
}
}
StringBuilder sb = new StringBuilder();
int tc = Integer.parseInt(br.readLine());
for(int i=0; i<tc; i++){
st = new StringTokenizer(br.readLine(), " ");
from = Integer.parseInt(st.nextToken());
to = Integer.parseInt(st.nextToken());
if(arr[from][to]>0 && arr[from][to]!=maxNum) sb.append("-1").append("\n");
else {
if(arr[to][from]>0 && arr[to][from]!=maxNum) sb.append("1").append("\n");
else sb.append("0").append("\n");
}
}
System.out.println(sb);
}
}
|
cs |
'백준 2 > 그래프' 카테고리의 다른 글
| [백준 10159] 저울 (0) | 2020.12.08 |
|---|---|
| [백준 1956] 운동 (C++/Java) (0) | 2020.12.08 |
| [백준 2660] 회장 뽑기 (0) | 2020.12.08 |
| [백준 1389] 케빈 베이컨의 6단계 법칙 (0) | 2020.12.08 |
| [백준 2668] 숫자 고르기 (0) | 2020.12.08 |