Эффективное представление списка смежности в C ++

Question

Стандартное представление списка смежности для взвешенных графов в C ++ представляет собой массив векторов пар часто (ie. vector<pair<int, int>> adj[N]). У меня нет проблем с этим, когда я знаю размер N во время компиляции, и если N не слишком большой. Однако, когда N известен только во время выполнения (переменная), мне приходится прибегать к тому, чтобы сделать N верхней границей размера списка смежности. Я часто сталкиваюсь с ошибками сегментации, где, если я не ошибаюсь, массив max_size превышен. Например, в настоящее время я сталкиваюсь с этой проблемой с границами N <= 3000 * 2999/2 (около 45000000). Ниже приведен пример с алгоритмом MST Прима, в котором я получаю ошибку сегментации. Как я могу избежать этого? Должен ли я рассмотреть другие типы данных? Спасибо! Изменить: я мог бы просто использовать вектор и инициализировать его с al oop от 1 до n, но мне интересно, есть ли более эффективный способ. </p>

int prims(int n, vector<vector<int>> edges, int start) {
vector<pair<int, int>> adj[45000000];
for(vector<int> edge : edges){
    adj[edge[0]].push_back({edge[2], edge[1]});
    adj[edge[1]].push_back({edge[2], edge[0]});
}
vector<bool> visited;
for(int i=0; i<n; i++){
    visited.push_back(false);
}
int dist = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start});
while(!pq.empty()){
    pair <int, int> p = pq.top();
    pq.pop();
    // cout << "top is " << p.second << "\n";
    if(visited[p.second]) continue;
    visited[p.second] = true;
    dist += p.first;
    for(pair<int, int> j : adj[p.second]){
        if(!visited[j.second]){
            pq.push(j);
        }
    }
}
return dist; }