BOJ#1613 역사

BOJ#1613 역사

* 문제

https://www.acmicpc.net/problem/1613

* 풀이

플로이드 와셜 알고리즘에 따라

Start -> 임의의 노드 -> End를 만족하는 임의의 노드가 존재할 때 (자기 자신을 포함하여)

Start -> End 를 만족함을 알 수 있습니다.

* 나의 코드

https://github.com/stack07142/BOJ/blob/644019c1ecb2b486c6597f4c2570edae8f97760f/BOJ%231613/src/Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        boolean[][] edges = new boolean[n][n];

        for (int i = 0; i < K; i++) {

            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;

            edges[a][b] = true;
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {

                    edges[i][j] |= edges[i][k] & edges[k][j];
                }
            }
        }

        int s = Integer.parseInt(br.readLine());

        for (int i = 0; i < s; i++) {

            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;

            if (edges[a][b]) System.out.println(-1);
            else if (edges[b][a]) System.out.println(1);
            else System.out.println(0);
        }
    }
}