Segmentation fault in C++ before entering main

Question

This is quite common question and I tried reading the solutions but none of them seem to fix my problem. Here is the code I wrote which I know is quite a mess because I am a newbie at C++.

#include<iostream>
#include<string>
#include<iomanip>
#include<set>
#include<queue>
#include<cmath>
#include<algorithm>
#include<vector>
#include<limits.h>
#include<math.h>
#include<map>
#include<cstring>
using ll = long long;
const int N = 2e6+6;

int main(){
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    int n,m;
    std::cin >> n >> m;
    std::vector<std::array<int,3>> edges;
    int exist[n][n];
    memset(exist,0,sizeof(exist));
    for(int i = 0; i < m;++i){
        int a,b;
        char c;
        std::cin >> a >> b >> c;
        --a,--b;
        edges.push_back({a,b,c-'a'});
        exist[a][b] = exist[b][a] = 1;
    }
    std::vector<int> adj[N];
    std::map<std::pair<int,int>,int> nodes;
    int node = 0;
    for(int i = 0; i < m;++i){
        for(int j = 0; j < m;++j){
            if(i == j)
                continue;
            if(edges[i][2] != edges[j][2])
                continue;
            int a = edges[i][0];
            int b = edges[i][1];
            int c = edges[j][0];
            int d = edges[j][1];
            if(nodes[{a,c}] == 0)
                nodes[{a,c}] = ++node;
            if(nodes[{b,d}] == 0)
                nodes[{b,d}] = ++node;
            if(nodes[{a,d}] == 0)
                nodes[{a,d}] = ++node;
            if(nodes[{b,c}] == 0)
                nodes[{b,c}] = ++node;
            adj[nodes[{a,c}]].push_back(nodes[{b,d}]);
            adj[nodes[{b,d}]].push_back(nodes[{a,c}]);
            adj[nodes[{a,d}]].push_back(nodes[{b,c}]);
            adj[nodes[{b,c}]].push_back(nodes[{a,d}]);
        }
    }
    int start = nodes[{0,n-1}];
    int ans = 1e9+7;
    std::queue<int> q;
    q.push(start);
    std::vector<int> dist(node+1,-1);
    dist[start] = 0;
    std::vector<bool> visited(node+1,false);
    visited[start] = true;
    auto it = nodes.begin();
    while(!q.empty()){
        int cur_node = q.front();
        q.pop();
        for(int i = 0; i < (int)adj[cur_node].size();++i){
            int next_node = adj[cur_node][i];
            if(!visited[next_node]){
                q.push(next_node);
                visited[next_node] = true;
                dist[next_node] = dist[cur_node] + 1;
            }
        }
    }
    for(int i = 0; i < n;++i){
        for(int j = 0; j < n;++j){
            int node = nodes[{i,j}];
            if(node == 0)
                continue;
            if(dist[node] == -1)
                continue;
            if(i == j || (exist[i][j] == 1)){
                ans = std::min(ans,dist[node]);
            }
        }
    }
    if(ans == 1e9+7)
        ans = -1;
    std::cout << ans << "\n";
}

This program gives segmentation fault even before entering main and I tried using gdb which also says that error is on the line int main() . I don't understand at all what is happening, and also I tried running the program on C++ 14 and C++ 17 and it runs fine but I am using C++ 11 and it compiles successfully but doesn't run. Please help me.

Answer 1

You’re allocating over two million std::vectors in your code in stack. Usually the stack isn’t very big so that most definitely will go over the reserved space and cause issues. The allocation for local objects happens before any code in the function is run so it will look like it crashes in the function but before any of your code is run.

std::vector<int> adj[N];

You’ll need to allocate it dynamically if you need that many vectors.

Answer 2

First, this is not valid C++:

int n;
cin >> n;
int exist[n][n];  // <-- not valid C++

Arrays in C++ must have their sizes denoted by a compile-time expression, not a runtime value. C++ does not support variable-length arrays.

The code compiled, since there are some compilers that by default, have support for this. But it still is not supported by the C++ language specification. For example, the Visual C++ compiler does not support this syntax. If you attempted to compile your code using Visual C++, you would be greeted with the appropriate error message.

Even if this is supported, a large value of n could potentially blow the stack memory, since the stack memory is limited.

Then the second issue is that you have this:

std::vector<int> adj[N];

If N is large, that is an array of N std::vector<int>. Again, this will more than likely exhaust the stack memory.

---

One solution is to use std::vector<std::vector<int>>:

std::vector<std::vector<int>> exist(n, std::vector<int>(n));
//...
std::vector<std::vector<int>> adj(N):

Since the vector gets its memory from the heap, the stack memory exhaustion issue goes away.