[白俊]#2458キー順

質問する

1番からN番まで番号が貼られていた生徒について、2人の生徒の身長を比較し、結果の一部を得た.しかし、N人とも身長が異なると仮定する.例えば、6人の生徒に対して身長を6回しか比較しなかった結果、以下のようになった.

1番学生の身長<5番学生の身長

3番学生の身長<4番学生の身長

5番学生の身長<4番学生の身長

4番学生の身長<2番学生の身長

4番学生の身長<6番学生の身長

5番学生の身長<2番学生の身長

この比較結果から、すべての生徒の中で、一番背の小さい生徒から自分が何位であるかを知ることができ、以下のような図を描いて自分が何位であるかを簡単に確認することができる.a番学生の身長がb番学生の身長より小さい場合は、aからbまでの矢印で表します.

1番は5番より低く、5番は4番より低いので、1番は4番より低いです.では、1番、3番、5番はいずれも4番未満です.また、4番が2番と6番より小さいので、4番には自分より小さい学生が3人、自分より大きい学生が2人いて、自分の身長が何位なのか正確に知ることができます.しかし、4番以外の生徒たちは自分の身長がどれくらいなのか分からない.
学生の身長を比較するときは、自分の身長を知っている学生が何人いるかを計算し、プログラムを書いてください.

入力

1行目は、生徒数N(2<=N<=500)と、2人の生徒の身長を比較した回数M(0<=M<=N(N−1)/2)を与える.次のM行は、2つの整数aおよびbを与え、2人の学生の身長を比較した結果を表す.これは、a番の学生がb番の学生より低いことを意味する.

しゅつりょく

自分の身長がどれくらい分かる学生が何人いるかを印刷します.

入力例1

6 6
1 5
3 4
5 4
4 2
4 6
5 2

サンプル出力1

1

に答える

この問題はfloydとshallアルゴリズムで解決できる.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int N;
    static int[][] map;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);

        map = new int[N+1][N+1];
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++)
                map[i][j] = 1000000;    //INF=1000000
        }

        for(int i=0; i<M; i++) {
            input = br.readLine().split(" ");
            map[Integer.parseInt(input[0])][Integer.parseInt(input[1])] = 1;
        }

        floyd_warshall();

        int[] cnt = new int[N+1];

        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(map[i][j]!=1000000) {    //키가 낮은 사람, 높은 사람을 모두 카운트 했을 때 전체-1 이면 순위 확정 가능
                    cnt[i]++;
                    cnt[j]++;
                }
            }
        }

        int ans = 0;
        for(int i=1; i<=N; i++) {
            if(cnt[i]==N-1)
                ans++;
        }

        System.out.println(ans);
    }

    public static void floyd_warshall() {         //플로이드 와샬 알고리즘 구현

        for(int k=1; k<=N; k++) {
            for(int i=1; i<=N; i++) {
                for(int j=1; j<=N; j++) {
                    map[i][j] = Math.min(map[i][j], map[i][k]+map[k][j]);
                }
            }
        }
    }
}