c++segmentation-faultlowest-common-ancestor

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


So, I was trying to solve the below problem using the most basic method i.e. storing the paths and finding LCA. My code is working fine on VSCode and giving the right output. But when submitting on SPOJ, it gives runtime error (SIGSEGV).

Problem Link: https://www.spoj.com/problems/LCA/

Problem Description:

A tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree. - Wikipedia

The lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with N nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself). - Wikipedia

Your task in this problem is to find the LCA of any two given nodes v and w in a given tree T.

Sample Input:

1
7
3 2 3 4
0
3 5 6 7
0
0
0
0
2
5 7
2 7

Sample Output:

Case 1:
3
1

My Code:

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

I think I'm not accessing any out of scope element so SIGSEGV should not occur.
Please tell me how can I fix and improve my code.


Solution

  • Some bugs are easy to find, when you know how to find them. The tools every programmer should know about are valgrind and -fsanitize. Remember to always compile with warnings enabled and fix them. Compiling your code with:

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

    results in a helpful warning:

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

    and a runtime error:

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

    Your storepath doesn't return value.