リンク

質問リンク

問題の説明

ボクシングの試合にはn人のボクサーが参加し、それぞれ1番からn番まで参加した.ボクシングの試合は1対1で行われ、A選手の実力がB選手より優れていれば、A選手はいつもB選手に勝つ.審判は与えられた試合の結果に基づいて選手をランキングしたいと思っている.しかし、いくつかの試合結果を失ったため、正確な順位はつけられなかった.
アスリートの数n,試合結果の2次元配列結果をパラメータとして与える場合は,正確に並べ替えられるアスリートの数を返すために解関数を記述してください.

せいげんじょうけん

選手の数は1名以上100名以下.

試合の結果は1試合以上4500試合以下であった.

その結果、各行[A,B]を並べてA選手がB選手に勝ったことを示す.

すべての試合の結果に矛盾はなかった.

I/O例

I/O例説明

2番選手は[1,3,4]選手に敗れ、5番選手が勝利したので4位だった.
5番は4位の2番に負けて5位だった

に答える

結果の勝敗情報をwin配列に整理する.

A選手がB選手、B選手がC選手に勝った時、A選手がC選手に勝ったので、A選手がB選手に勝った時、B選手の勝敗情報はA選手に更新されます.

しかし重要なのはA選手がB選手に負けた時、A選手の勝利情報もB選手に移ることだ.(テストケース2、7、8)

2,3回の経過後、n-1の勝敗情報があれば++と答えてください!

この問題によりfloodとshallというアルゴリズムを知り,ノード数が少ないと三重砲口を回転させる勇気を得た.
でもTEKE 2,7,8大変だったのでもう少しで髪の毛が抜けるところでした~

コード#コード#

import java.util.*;
class Solution {
    static boolean [][] win;
    public int solution(int n, int[][] results) {
        int answer = 0;
        win = new boolean[n + 1][n + 1];
        for(int i = 0; i < results.length; i++) 
            win[results[i][0]][results[i][1]] = true;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(win[i][j])
                {
                    for(int k = 1; k <= n; k++) {
                        win[i][k] |= win[j][k];
                    }
                }
                if(win[j][i])
                {
                    for(int k = 1; k <= n; k++) {
                        win[j][k] |= win[i][k];
                    }
                }
            }
        }
        int cnt;
        for(int i = 1; i <= n; i++){
            cnt = 0;
            for(int j = 1; j <= n; j++){
                if(win[i][j] | win[j][i])
                    cnt++;
            }
            if(cnt == n - 1)
                answer++;
        }
        return answer;
    }
}