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.
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.