I’d like to understand why this code runs so slowly

Question

I've written a code, maybe an easy coding test. (details under)

boxers play matches

better man always win ex) if A boxer is better than B, A always wins B if C boxer is better than A, C always wins A, B

So, always (C > A > B), never (C > A > B > C) things.

After the competition ends, some match results are missing. Given the results you have, determine how many boxers can be definitively ranked.

*constrains
i)  1 <= boxers <= 100.
ii)  1 <= results.size() <= 4500, results contains match_data.
iii) match_data [A, B] means (A defeated B).
iV) no contradictions in the data: if [A,B] exist, [B,A] does not.

----------------------------------------------------------------------

N of boxer                       results                          answer

    5             [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]      2

-----------------------------------------------------------------------

                        [[  explain  ]]

In this situation, u can construct two rank-chains.

4 > 3 > 2 > 5 1 > 2 > 5

Here, 2, 5 can confirm their rank 4th, 5th respectively But, 4, 3, 1 can't confirm their relative rank due to missing data.

Thus, answer is 2;

my code below

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int win = 0;
int lose = 1;

int solution(int n, vector<vector<int>> results) {

    queue<pair<int, int>> q;

    vector<vector<vector<int>>> Graph(n, vector<vector<int>>(2));

    vector<int> rating = vector(n,0);

    vector<vector<vector<int>>> List(n, vector<vector<int>>(2, vector<int>(n, 0)));


    for(int match=0; match < results.size(); match++){

        int winner = results[match][win]-1;
        int loser = results[match][lose]-1;

        Graph[winner][win].push_back(loser);
        Graph[loser][lose].push_back(winner);
    
    }

    for(int index=0; index<n; index++){
    
        if(Graph[index][win].size() == 0 && Graph[index][lose].size() == 0) return 0;
    
        if(Graph[index][win].size() == 0){
            for(int i=0; i<Graph[index][lose].size(); i++){
                q.push({Graph[index][lose][i], index});
            }
            while(!q.empty()){
                auto [winner, loser] = q.front();
                q.pop();
            
                if(List[winner][win][loser]==0){
                    List[winner][win][loser] = 1;
                    rating[winner]++;
                }
            
            
                for(int j=0; j<n; j++){
                    if(List[loser][win][j] == 1 && List[winner][win][j] == 0){
                        List[winner][win][j] = 1;
                        rating[winner]++;
                    }
                }
            
                for(int j=0; j<Graph[winner][lose].size(); j++){
                    q.push({Graph[winner][lose][j], winner});
                }
            }
        }
    
        if(Graph[index][lose].size() == 0){
            for(int i=0; i<Graph[index][win].size(); i++){
                q.push({Graph[index][win][i], index});
            }
         
            while(!q.empty()){
                auto [loser, winner] = q.front();
                q.pop();
                
                if(List[loser][lose][winner]==0){
                    List[loser][lose][winner] = 1;
                    rating[loser]++;
                }
                
            
                for(int j=0; j<n; j++){
                    if(List[winner][lose][j] == 1 && List[loser][lose][j] == 0){
                        List[loser][lose][j] = 1;
                        rating[loser]++;
                    }
                }
            
                for(int j=0; j<Graph[loser][win].size(); j++){
                    q.push({Graph[loser][win][j], loser});
                }
            }
        }
    }

    int answer = 0;
    for(int index=0; index<n; index++){
        //cout << rating[index] << ", ";
        if(rating[index]==n-1){
            answer++;
        }
    }

    return answer;

}

My code works, and I expected that complexity of my code is O(n^2+n⋅m) << n = boxer number, m = results.size() >>

When given a lot of data, it still works but takes too long time.

I found that Floyd-Warshall Algorithm works much better.

Even so, I really want to know why my code takes so much time and what its actual time complexity is.

1. Thank you for taking the time to read and help.

Answer 1

Not related to time-complexity, but two observations affecting the performance of your code:

First, how you passing the data:

int solution(int n, vector<vector<int>> results) {

This creates an unnecessary copy of the input-data. Better to pass by const&. Doesn't affect the time of the main loop, but creates avoidable allocations at the start.

Second, some of your data-structures can be improved:

vector<vector<vector<int>>> Graph(n, vector<vector<int>>(2));

As some of your data-sizes are unknown, having some nested vectors make sense. However, the second vector in the chain is always accessed via either 0 or 1, so it can be replaced by an array without requiring modifying the rest of the code:

vector<array<vector<int>, 2>> Graph(n);

Has the nice side-effect of also making the initialization a bit less clunky. But mainly, it will remove one indirection in accessing the data, as well as some unnecessary allocations. The shame should apply to "List" too. So in general, it's a good idea to use fixed-sized arrays when you know the size upfront, instead of vector (which is designed to hold varying sizes, but pays for that with slightly less optimal memory layout and allocations).