Code running fine on my system but segmentation fault on HackerRank submission

Question

I'm doing a coding problem on hackerrank and my code is running successfully on my system but giving segmentation fault while submitting the solution. Please help me out. Have stuck for hours in it. But not able to find the issue.

HackerRank Question: https://www.hackerrank.com/challenges/torque-and-development

This is my code:

#include <bits/stdc++.h>

using namespace std;

int n,m,cRoad,cLib;

void initialize(bool visited[])
{
    int i ;
    for(i=0;i<=n;i++)
    {
        visited[i] = false ;
    }
}

void  dfs(vector <int> arr[],bool visited[],int node,int &numOfNodes)
{
    int i,j;
    for(i=0;i<arr[node].size();i++)
    {
        if(visited[arr[node][i] ] == false )
        {
            visited[arr[node][i] ] = true ;
            dfs(arr,visited,arr[node][i],numOfNodes);
        }

    }
    numOfNodes ++ ;
}

int minCost(vector <int> arr[],bool visited[])
{
    int cost = 0;
    int i , connectedComponents =0;
    if(cLib < cRoad)
        return (n * cLib);
    else
    {
        for(i=1;i<=n;i++)
        {
          int numOfNodes = 0 ;

          if(visited[i]==false)
          {
              dfs(arr,visited,i,numOfNodes);
              connectedComponents++;
              cost += (numOfNodes - 1 ) * cRoad + cLib ;
          }
        }
        return cost ;
    }
}

int main()
{
  int q,u,v,i,j;
  scanf("%d",&q);

  while(q--)
  {
      scanf("%d %d %d %d",&n,&m,&cLib ,&cRoad);
      vector <int> arr[n];
      bool visited[n];
      initialize(visited);

      for(i=0;i<m;i++)
      {
          scanf("%d %d",&u,&v);
          arr[u].push_back(v);
          arr[v].push_back(u);
      }
      cout<<minCost(arr,visited);
  }
}

Sample Input:

Sample Output:

4
12

Error on Hackerrank:

GDB trace:

Reading symbols from solution...done.

[New LWP 14235]

Core was generated by `solution'.

Program terminated with signal SIGSEGV, Segmentation fault.

/#0 0x00000000004009d9 in __gnu_cxx::new_allocator::construct (this=0x7ffdbd2b9738, __p=0x1)

at /usr/include/c++/6/ext/new_allocator.h:120

120 { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }

/#0 0x00000000004009d9 in __gnu_cxx::new_allocator::construct (this=0x7ffdbd2b9738, __p=0x1)

at /usr/include/c++/6/ext/new_allocator.h:120

/#1 std::allocator_traits >::construct

(

__a=..., __p=0x1) at /usr/include/c++/6/bits/alloc_traits.h:455

/#2 std::vector >::push_back (

__x=@0x7ffdbd2b9754: 1, this=0x7ffdbd2b9738)

at /usr/include/c++/6/bits/stl_vector.h:918

/#3 main () at solution.cc:76

first off: "vector <int> arr[n];" does not create a vector<int> of size n, it creates an array of size n of vector<int>. you should change it to "vector <int> arr(n);" — Rob
No you are not at least the code you have posted does not :). just like <datatype> a[n]; creates a memory location that is n times the size of the datatype and initialize n instance of data in it, and stores the address of the beginning of that block of memory in the variable a. so your datatype happens to be vector<int>. use a debugger you will see. the correct syntax is vector<int> a(n); — Rob
example: I did vector<int> a(n); and vector<int> b[n]: and in gdb this is how those data elements are printed when initialized with n =2 — Rob
(gdb) print a $1 = {<std::_Vector_base<int, std::allocator<int> >> = { _M_impl = {<std::allocator<int>> = {<__gnu_cxx::new_allocator<int>> = {<No data fields>}, <No data fields>}, _M_start = 0x60005bc60, _M_finish = 0x60005bc68, _M_end_of_storage = 0x60005bc68}}, <No data fields>} — Rob

Šimon Hrabec Šimon Hrabec · Accepted Answer · 2017-05-17T13:31:10

It would be easier to understand the code if you have provided the hackerrank assignment or documented your code or named variables unlike q,u,v,i,j. From what I see you are trying

  vector <int> arr[n];
  bool visited[n];

Which should initialize the array. However you are using static array and try to initialize it dynamically. Therefore you should use dynamic array (dynamically allocate memory) or rather use fixed array of sufficient as it is common in competitive programming or use container such as vector, which encapsulates all dynamic memory management.

I also see in your code various loops:

for(i=0;i<=n;i++)
for(i=1;i<=n;i++)
for(i=0;i<m;i++)

It is possible to have a bug there. I would use either a 0 indexing a 1 indexing over the whole program (some people actually use 1 in competitive programming).

If you compile your code with -Wall -pedantic flags, you will get following warnings:

so.cpp: In function ‘void dfs(std::vector<int>*, bool*, int, int&)’:
so.cpp:19:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<arr[node].size();i++)
                              ^
so.cpp:18:11: warning: unused variable ‘j’ [-Wunused-variable]
     int i,j;
           ^
so.cpp: In function ‘int main()’:
so.cpp:62:25: warning: ISO C++ forbids variable length array ‘arr’ [-Wvla]
       vector <int> arr[n];
                         ^
so.cpp:63:21: warning: ISO C++ forbids variable length array ‘visited’ [-Wvla]
       bool visited[n];
                     ^
so.cpp:56:15: warning: unused variable ‘j’ [-Wunused-variable]
   int q,u,v,i,j;

The reason why you get segmentation fault is because you are going out of the array bounds. Have array that has 3 elements and you are trying to access it at index 3 (which is 4th element). It can run successfully on your PC, since accessing memory behind (of before) the array will yield into undefined behavior.

Btw it is good practice to declare variable as late as possible, at the palce where you are going to use them. There is no need to declare i (loop control variable) at the begging of function. It is better to have it only in the for cycle so it does not go out of scope.

Code running fine on my system but segmentation fault on HackerRank submission

2 Answers