针对给定问题获取 SIGSEGV（分段错误）。（寻找通用树的 LCA）

Question

所以，我试图使用最基本的方法解决以下问题，即存储路径和查找 LCA。我的代码在 VSCode 上运行良好并提供正确的输出。但是在 SPOJ 上提交时会出现运行时错误 (SIGSEGV)。

问题Link：https://www.spoj.com/problems/LCA/

问题描述:

树是一种无向图，其中任意两个顶点仅由一条简单路径连接。换句话说，任何没有循环的连通图都是一棵树。 - 维基百科

最低共同祖先 (LCA) 是图论和计算机科学中的一个概念。令 T 为具有 N 个节点的有根树。最低公共祖先定义在两个节点 v 和 w 之间，作为 T 中同时具有 v 和 w 作为后代的最低节点（我们允许节点是其自身的后代）。 - 维基百科

你在这个问题中的任务是找到给定树 T 中任意两个给定节点 v 和 w 的 LCA。

示例输入：

示例输出：

Case 1:
3
1

我的代码：

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;

vector<vector<int>> edges;

bool storepath(int s, int d,  vector<int>& path, vector<bool>& visited) {
   if(s == d)
   {
       path.push_back(d);
       return true;
   }

   else if(edges[s].size() == 1) {
       if(s != d)
       {
           for(int i = 0; i < path.size(); i++)
               if(path[i] == s) {
                   path.erase(path.begin() + i);
               }
       }
       return false;
   }

   visited[s] = true;
   path.push_back(s);
   for(auto e: edges[s])
   {
       if(visited[e] == false)
       { 
           bool ans = storepath(e, d, path, visited);
           if(ans)
               break;
       }
   }
}

int LCA(int a, int b)
{
   if(a == b)
       return a;
   vector<int> path1, path2;

   vector<bool> visited(edges.size(), false);
   storepath(1, a, path1, visited);
   visited.assign(edges.size(), false);
   storepath(1, b, path2, visited);

   int n = path1.size();       
   int m = path2.size();

   int i = 0,j = 0;
   while(i < n && j < m && path1[i] == path2[j]) {
       i++;
       j++;
   }

   return path1[i-1];
}

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);cout.tie(0);

   int t;
   cin >> t;
   int Case = 1;
   while(t--)
   {
       int n;
       cin >> n;
       
       edges.resize(n+1);
       for(int i = 1; i <= n; i++)
       {
           int size, val;
           cin >> size;
           while(size--)
           {
               cin >> val;
               edges[i].push_back(val);
               edges[val].push_back(i);
           }
       }


       int q;
       cin >> q;
       cout << "Case "<< Case << ":" << endl;
       while(q--)
       {
           int a, b;
           cin >> a >> b;
           cout << LCA(a, b) << endl;
       }
       Case++;
       edges.clear(); //added after igor's comment (forgot to add before but used while submitting)
   }

   return 0;   
}

我认为我没有访问任何超出范围的元素，因此不应出现 SIGSEGV。
请告诉我如何修复和改进我的代码。

Answer 1

有些错误很容易找到，只要您知道如何找到它们。每个程序员都应该知道的工具是 valgrind 和 -fsanitize。请记住始终在启用警告的情况下进行编译并修复它们。使用以下代码编译代码：

g++ -Wall -Wextra -fsanitize=undefined 1.cpp && ./a.out </tmp/2

产生有用的警告：

1.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

和一个运行时错误：

1.cpp:9:6: runtime error: execution reached the end of a value-returning function without returning a value

你的 storepath 没有 return 值。

针对给定问题获取 SIGSEGV（分段错误）。（寻找通用树的 LCA）

Getting SIGSEGV (segmentation error) for the given problem. (Finding LCA of a generic tree)

c++

segmentation-fault

lowest-common-ancestor

针对给定问题获取 SIGSEGV（分段错误）。 （寻找通用树的 LCA）

Getting SIGSEGV (segmentation error) for the given problem. (Finding LCA of a generic tree)

c++

segmentation-fault

lowest-common-ancestor

针对给定问题获取 SIGSEGV（分段错误）。（寻找通用树的 LCA）