[BOJ] 2458. 키 순서

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

접근 방법

플로이드 와샬을 사용했다.

간선을 추가했을 때 이것이 키 비교가 가능한지 판단만 하면된다.

그리고 마지막에 순서를 뒤짚었을 때 가능한지도 확인 하면 된다.

Need Know

1. 플로이드와샬

전체 코드 ( Java )

import java.io.*;
import java.util.StringTokenizer;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int M;
    static int ans;
    static boolean[][] map;
    public static void main(String[] args) throws IOException {
        set();

        solve();
        bw.flush();
        bw.close();
        br.close();
    }
    static void set() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new boolean[N+1][N+1];
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a][b] = true;
        }
    }

    static void solve() throws IOException {
        for (int i = 1; i < N + 1; i++) {
            for (int k = 1; k < N + 1; k++) {
                for (int e = 1; e < N+1; e++) {
                    if(map[k][i] && map[i][e]){
                        map[k][e] = true;
                    }
                }
            }
        }

        int[] tempAns = new int[N+1];
        for(int i=1; i<N+1; i++){
            for(int k=1; k<N+1; k++){
                if(map[i][k] || map[k][i]) {
                    tempAns[i]++;
                }
            }
        }
        for(int i=1; i<N+1; i++){
            if(tempAns[i] == N-1) ans++;
        }
        bw.write(ans+"");
    }
}