ランキングC++

問題の説明

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

せいげんじょうけん

選手の数は1名以上100名以下です.
試合結果は1個以上4500個以下であった.
その結果、各行[A,B]に並んでA選手がB選手に勝ったことを示す.
すべての試合の結果に矛盾はなかった.

問題を解く

個人的には難しいと思います.その結果、ネットで検索して分かったのですが、手順を説明するには、まず練習帳の上の小さいものから自分でやったことがあります.
そこから得られたアルゴリズムは,n-1試合でゲームの勝敗が分かれば順位を決めることができる.しかし、上記の例のように5と2は1試合しか行われなかったが、最下位の明確な順位が分かったので、どうすればいいのか悩んだが、自分では答えが出せなかった.
だから検索にFlood-Whallアルゴリズムを使いましたか?やった、ははは、フロイドとシエルアルゴリズムは最短距離を知るためのアルゴリズムではないでしょうか.だからもう一度勉強して整理しましょう.

floydとshallアルゴリズム

前の問題では,floydとshallがすべての頂点からすべての頂点への最短経路を探す際に用いられるアルゴリズムをグラフィック問題タイプ別に用いたアルゴリズムをまとめた.他のアルゴリズムと比較して、アルゴリズムは通過した頂点に基づいて実行される.
例えば、1−>3の直接コストが8であれば、1−>2−>3のコストが8未満であれば、1−>3のコストを更新するアルゴリズムである.すなわち
XからYまでの最低コストvs XからZノードからYまでのコスト

//k = 거쳐가는 노드
for(int k = 0 ; k < n ; k++)
{
	//i = 출발 노드
    for(int i = 0; i<n ; i++)
    {
    	//j = 도착 노드
        for(int j = 0; j < n ; j++)
        {
        	if(node[i][k] + node[k][j] < node[i][j])
            	node[i][j] = node[i][k] + node[k][j];
        }
    }
}

フロイドとシエルのアルゴリズムを考察しても、なぜこの問題でこのアルゴリズムを使うのか分からない.😥
この場合、少なくともこのアルゴリズムは理解されており、1,2,3,4,5名の選手がいる場合には、1と2との単純なパス(試合)ではなく、1とこれまでに通ってきたノード(相手)とのパス(試合)で2との勝負となる.

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<vector<bool>> res(n+1,vector<bool>(n+1,false));
    
    for(int i = 0 ; i < results.size(); i ++)
    {
        int winner = results[i][0];
        int loser = results[i][1];
        res[winner][loser] = true;
    }
    
    for(int k = 1; k < n+1 ; k++)
    {
        for(int i = 1; i < n+1; i++)
        {
            for(int j = 1; j < n+1; j++)
            {
                if(res[i][k] && res[k][j])
                    res[i][j] = true;
            }
        }
    }
    
    for(int i = 1; i < n +1 ; i ++)
    {
        int cnt = 0;
        for (int j = 1; j < n+1 ; j ++)
        {
            if(res[i][j] || res[j][i])
                cnt++;
        }
        if (cnt == n-1)
            answer ++;
        
    }
    
    return answer;
}