Run time error in graph

Question

I am implementing Graph for the first time and for that I took this problem from SPOJ.

Took help of geeksforgeeks, applied union find algorithm to find out whether or not graph contains a cycle but I get run time error (SIGSEGV).

Can you please help why is it so?

#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->v;i++)
      cout<<"p"<<i<<"="<<p[i];
  cout<<"\n";*/
 for(int i=0;i<graph->e;i++)
 {
      /*cout<<"edge"<<i<<" src="<<graph->edge[i].s<<"\n";
      cout<<"edge"<<i<<" dest="<<graph->edge[i].d<<"\n";*/
      int x=Find(p,graph->edge[i].s);
      int y=Find(p,graph->edge[i].d);
      /*cout<<"x="<<x<<" "<<"y="<<y<<"\n";*/
      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";
 }
}

Answer 1

One issue is this in your main program:

graph->edge[i].s=v1-1;

You created a single edge. If i is greater than 0, then this is an out-of-bounds access.

Look how you created edge in the create function:

 graph->edge=(struct Edge*)malloc(sizeof (struct Edge));

That allocation holds a single edge, not multiple edges. Given how you coded the rest of your program in a C-like fashion, what you probably wanted is this:

 graph->edge=(struct Edge*)malloc(sizeof(Edge) * e);

Also, you should strive to not use single-letter variable names. It is hard to read code with e, v, etc. as member variable names. Name those items m_edge, m_vertex or something that is more descriptive.