# SPOJ Is it a tree SIGSEGV.

Hola! I’ve been trying to implement graph for the first time and the question for which I’m implementing is this. But, I have no idea why am I encountering RTE (SIGSEGV) again and again. Here’s the code that I have learned from geeksforgeeks for union-find algorithm. Please point out the mistake in implementation.

``````#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;

struct Edge{
int s,d;
};
struct Graph{
int v,e;
struct Edge* edge;
};
struct Graph* create(int v, int e){
struct Graph* graph=(struct Graph*)malloc(sizeof (struct Graph));
graph->v=v;
graph->e=e;
graph->edge=(struct Edge*)malloc(sizeof (struct Edge));
return graph;
};
int Find(int p[],int i)
{
if (p[i] == -1)
return i;
return Find(p, p[i]);
}
void Union(int p[],int i, int j)
{
p[j]=i;
}
bool CheckCycle(struct Graph* graph)
{
int *p=(int*)malloc(graph->v* sizeof (int));
memset(p,-1,graph->v * sizeof (int));
for(int i=0;i<graph->e;i++)
{
int x=Find(p,graph->edge[i].s);
int y=Find(p,graph->edge[i].d);
if(x==y)
return true;
Union(p,x,y);
}
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
int N,M,v1,v2;
cin>>N>>M;
if(M!=(N-1))
cout<<"NO\n";
else{
struct Graph* graph=create(N,M);
for(int i=0;i<M;i++)
{
cin>>v1;
graph->edge[i].s=v1-1;
cin>>v2;
graph->edge[i].d=v2-1;
}
if(CheckCycle(graph))
cout<<"NO\n";
else
cout<<"YES\n";
}
}
``````

It is a case of segmentation fault.

There is no need of making a graph for this question. You can just make a bool array which checks that if there is a loop it breaks and prints NO, else prints YES.

It looks like this–

f = true

bool nodes[MAX] = {0}

while(m–){ //m = no. of test cases

s(a);s(b); // take input a,b

if((nodes[a]!=0) && (nodes[b]!=0)){

`````` f = false;break;
``````

}

else{

``````     if(!nodes[a]) nodes[a]=1;

if(!nodes[b]) nodes[b] = 1;

}
``````

}

Also take care if some inputs are left don’t forget to take them otherwise it will give NZEC error.

if (f) print YES
else print NO

I hope this helps you in understanding the tree topology better.

Hi @adi28galaxyak! Thanks for the idea but I wanted to learn how to implement a graph so did it this way. I’ve just found the bug. Thank you for effort in explaining.

Instead of this you can check if(vertices==edges-1 && graph is connected).
For checking graph is connected or not you have to traverse graph (dfs/bfs) then check every vertex visited or not.

//