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

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.

//