erreur d'exécution: liaison de référence à un pointeur nul de type 'std :: vector <int, std :: allocator <int>>' (stl_vector.h)

Question

Ceci est leetcode 210
Il y a un total de n cours que vous devez suivre étiquetés de 0 à n - 1.

Certains cours peuvent avoir des prérequis, par exemple, si les prérequis [i] = [ai, bi] cela signifie que vous devez suivre le cours bi avant le cours ai.

Compte tenu du nombre total de cours, du nombre de cours et d'une liste des paires de prérequis, renvoyez l'ordre des cours à suivre pour terminer tous les cours.

S'il existe de nombreuses réponses valides, renvoyez l'une d'entre elles. S'il est impossible de terminer tous les cours, renvoyez un tableau vide.

Entrée: numCourses = 4, prérequis = [[1,0], [2,0], [3,1], [3,2]] Sortie: [0,2,1,3]

Chaque fois que je soumets ce code ci-dessous, runtime error: reference binding to null pointer of type 'std::vector<int, std::allocator<int> >' (stl_vector.h)j'apprécierais si quelqu'un pouvait m'aider avec cela!

class Solution {
public:
    vector<int> adj[2002];
    bool vis[2002];
    vector <int> myvect;
    void dfs(int node)
    {
        if(!vis[node])
        {
          for(int i = 0; i < (int)adj[node].size(); i++)
          {
              if(!vis[adj[node][i]])
                  dfs(vis[adj[node][i]]);
          }
           myvect.push_back(node);
        }
        
        
    }
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites)
    {
       
        vector<int> adj[2002];
        int n = prerequisites.size();
        int m = prerequisites[0].size(); 
        if(n == 0 && m == 0)
        {
            for(int i = 0; i < numCourses; i++){
                myvect.push_back(i);
            }
            return myvect;
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
                adj[i].push_back(j);
        }
        
        for(int i = 0; i < numCourses; i++)
            dfs(i);
        return myvect;
        
        
    }
};

Answer 1

• Vous n'avez qu'une petite faute de frappe ici: return vectto return myvect.

• Un autre petit bug est ici: int m = n ? prerequisites[0].size() : 0;

• Après avoir corrigé ces bogues, l'algorithme fonctionne partiellement correctement, ne fonctionne pas pour tous les cas de test, je ne sais pas comment résoudre cela. (ˆ_ˆ)

class Solution {
    public:
        vector<int> adj[2002];
        bool vis[2002];
        vector <int> myvect;
        void dfs(int node) {
            if (!vis[node]) {
                for (int i = 0; i < (int)adj[node].size(); i++) {
                    if (!vis[adj[node][i]]) {
                        dfs(vis[adj[node][i]]);
                    }
                }

                myvect.push_back(node);
            }


        }
        vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {

            vector<int> adj[2002];
            int n = prerequisites.size();
            int m = n ? prerequisites[0].size() : 0;

            if (n == 0 && m == 0) {
                for (int i = 0; i < numCourses; i++) {
                    myvect.push_back(i);
                }

                return myvect;
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    adj[i].push_back(j);
                }
            }

            for (int i = 0; i < numCourses; i++) {
                dfs(i);
            }

            return myvect;


        }
};

• Cela mis de côté, nous pouvons également nommer nos variables peut-être un peu plus descriptif:

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>

using ValueType = std::uint_fast16_t;
using Graph = std::vector<std::vector<ValueType>>;

static const struct Solution {
        static const std::vector<int> findOrder(
            const int num_courses,
            const std::vector<std::vector<int>>& prerequisites
        ) {
            const Graph graph = buildGraph(num_courses, prerequisites);
            std::vector<ValueType> indegrees = getIndegrees(graph);
            std::vector<int> orders;

            for (ValueType i = 0; i < num_courses; ++i) {
                ValueType j = 0;

                for (; j < num_courses; j++) {
                    if (!indegrees[j]) {
                        orders.emplace_back(j);
                        break;
                    }
                }

                if (j == num_courses) {
                    return {};
                }

                --indegrees[j];

                for (const auto& edge : graph[j]) {
                    --indegrees[edge];
                }
            }

            return orders;
        }

    private:
        
        static const Graph buildGraph(
            const int num_courses,
            const std::vector<std::vector<int>>& prerequisites
        ) {
            Graph graph(num_courses);

            for (const auto& prerequisite : prerequisites) {
                graph[prerequisite[1]].emplace_back(prerequisite[0]);
            }

            return graph;
        }

        static const std::vector<ValueType> getIndegrees(
            const Graph& graph
        ) {
            std::vector<ValueType> indegrees(std::size(graph), 0);

            for (const auto& adj_edges : graph) {
                for (const auto& edge : adj_edges) {
                    ++indegrees[edge];
                }
            }

            return indegrees;
        }

};