So, I was trying to solve this problem using the most basic method i.e. storing the paths and finding LCA.
My code is working fine in VSCode and giving the right output. But when submitting here. It gives runtime error (SIGSEGV).
This is the 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+100);
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++;
}
return 0;
}
I’m not sure where I’m going wrong. Please have a look.
I tried debugging using cout statements:
This is the code for debugging:
#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;
vector<vector<int>> edges;
void print(vector<int>& v) {
cout << endl << "-----------------" << endl;
for(int i = 0; i < v.size(); i++)
cout << v[i] << " ";
cout << endl << "-----------------" << endl;
}
void printedges() {
cout << endl << "-------Printing Edges---------" << endl;
for(int i = 1; i < edges.size(); i++) {
cout << i << ": ";
for(int j = 0; j < edges[i].size(); j++) {
cout << edges[i][j] << " ";
}
cout << endl;
}
cout << endl << "------------------------------" << endl;
}
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;
}
cout << "storepath" << endl;
visited[s] = true;
cout << "pushing " << s <<"!"<< endl;
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;
cout << "in lca" << endl;
vector<int> path1, path2;
cout << "a: " << a << endl;
cout << "b: " << b << endl;
vector<bool> visited(edges.size(), false);
cout << endl;
cout << "-------------------call 1---------------------" << endl;
storepath(1, a, path1, visited);
visited.assign(edges.size(), false);
cout << "-------------------call 2---------------------" << endl;
storepath(1, b, path2, visited);
cout << endl;
int n = path1.size();
int m = path2.size();
print(path1);
print(path2);
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;
cout << "size: " << size << endl;
while(size--)
{
cin >> val;
edges[i].push_back(val);
edges[val].push_back(i);
cout << "i: " << i << endl;
cout << "val: " << val << endl;
for(int j = 0; j < edges[i].size(); j++)
cout << "edges[" << i << "]: " << edges[i][j] <<endl;
}
}
printedges();
int q;
cin >> q;
cout << "Case " << Case << ": " << endl;
while(q--)
{
int a, b;
cin >> a >> b;
cout << "in while s" << endl;
cout << LCA(a, b) << endl;
cout << "in while e" << endl;
}
Case++;
}
return 0;
}
For this test case:
1
7
3 2 3 4
0
3 5 6 7
0
0
0
0
2
5 7
2 7
The output on ideone is:
size: 3
i: 1
val: 2
edges[1]: 2
i: 1
val: 3
edges[1]: 2
edges[1]: 3
i: 1
val: 4
edges[1]: 2
edges[1]: 3
edges[1]: 4
size: 0
size: 3
i: 3
val: 5
edges[3]: 1
edges[3]: 5
i: 3
val: 6
edges[3]: 1
edges[3]: 5
edges[3]: 6
i: 3
val: 7
edges[3]: 1
edges[3]: 5
edges[3]: 6
edges[3]: 7
size: 0
size: 0
size: 0
size: 0
-------Printing Edges---------
1: 2 3 4
2: 1
3: 1 5 6 7
4: 1
5: 3
6: 3
7: 3
------------------------------
Case 1:
in while s
in lca
a: 5
b: 7
-------------------call 1---------------------
storepath
pushing 1!
storepath
pushing 3!
storepath
pushing 0!
If you see the last line. It is pushing 0. This should not happen.
Please check it. Thank you!