c++ - 代码在我的系统上运行良好，但在提交 HackerRank 时出现段错误

Question

我在 hackerrank 上做一个编码问题，我的代码在我的系统上成功运行，但在提交解决方案时出现段错误。请帮帮我。已经在其中停留了几个小时。但找不到问题。

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

这是我的代码:

#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);
  }
}

示例输入:

2
3 3 2 1
1 2
3 1
2 3
6 6 2 5
1 3
3 4
2 4
1 2
2 3
5 6

示例输出:

4
12

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

Answer 1

如果您提供了 hackerrank 分配或记录了您的代码或与 q,u,v,i,j 不同的命名变量，将会更容易理解代码。据我所见，您正在尝试

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

应该初始化数组。但是，您使用的是静态数组并尝试动态初始化它。因此，您应该使用动态数组(动态分配内存)，或者更确切地说，使用足够的固定数组，因为它在竞争性编程中很常见，或者使用诸如 vector 之类的容器，它封装了所有动态内存管理。

我还在你的代码中看到了各种循环:

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

那里可能有错误。我会在整个程序中使用 0 索引和 1 索引(有些人实际上在竞争性编程中使用 1)。

如果您使用 -Wall -pedantic 标志编译您的代码，您将收到以下警告:

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;

出现段错误的原因是因为您超出了数组边界。拥有包含 3 个元素的数组，您正试图在索引 3(即第 4 个元素)处访问它。它可以在您的 PC 上成功运行，因为访问数组后面(之前)的内存会产生未定义的行为。

顺便说一句，最好在您要使用它们的地方尽可能晚地声明变量。无需在函数开头声明 i(循环控制变量)。最好只在 for 循环中使用它，这样它就不会超出范围。