[백준] 1613번 역사

[적용한 알고리즘]

플로이드-와샬

 

[아이디어]

x->y 로 가는 경로가 있는가?

y->x 로 가는 경로가 있는가?

둘 다 없는가? 

 

를 알아보면 되겠다.

 

 

<코드>

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 401;

bool dist[MAX_N][MAX_N];
int main(){
    int N, K;
    scanf("%d %d", &N, &K);

    for (int i = 0; i < K; i++){
        int first, second;
        scanf("%d %d", &first, &second);
        dist[first][second] = true;
    }

    for (int k = 1; k <= N; k++){
        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= N; j++){
                if (dist[i][k] && dist[k][j]){
                    dist[i][j] = true;
                }
            }
        }
    }

    int Q;
    scanf("%d", &Q);

    while (Q--){
        int x, y;
        scanf("%d %d", &x, &y);
        if (dist[x][y]) printf("-1\n");
        else if (dist[y][x]) printf("1\n");
        else printf("0\n");
    }
    return 0;
}