runtime error: referensi mengikat ke pointer nol tipe 'std :: vector <int, std :: alokator <int>>' (stl_vector.h)

Question

Ini adalah leetcode 210
Ada total n kursus yang harus Anda ambil berlabel dari 0 hingga n - 1.

Beberapa mata kuliah mungkin memiliki prasyarat, misalnya jika prasyarat [i] = [ai, bi] ini berarti anda harus mengikuti mata kuliah bi sebelum mata kuliah ai.

Dengan melihat jumlah total mata kuliah dan daftar pasangan prasyarat, kembalikan urutan mata kuliah yang harus Anda ambil untuk menyelesaikan semua mata kuliah.

Jika ada banyak jawaban yang valid, kembalikan salah satunya. Jika tidak mungkin untuk menyelesaikan semua kursus, kembalikan array kosong.

Masukan: numCourses = 4, prasyarat = [[1,0], [2,0], [3,1], [3,2]] Keluaran: [0,2,1,3]

Kapan pun saya mengirimkan kode ini di bawah, saya mendapatkan pesan runtime error: reference binding to null pointer of type 'std::vector<int, std::allocator<int> >' (stl_vector.h)Akan sangat menghargai jika seseorang dapat membantu saya dengan ini!

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

• Anda hanya memiliki kesalahan ketik kecil di sini: return vectuntuk return myvect.

• Bug kecil lainnya ada di sini: int m = n ? prerequisites[0].size() : 0;

• Setelah memperbaiki bug ini, algoritme sebagian berfungsi dengan baik, tidak berfungsi untuk semua kasus pengujian, tidak yakin bagaimana cara memperbaikinya. (ˆ_ˆ)

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;


        }
};

• Selain itu, kami juga dapat memberi nama variabel kami mungkin sedikit lebih deskriptif:

// 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;
        }

};