Ошибка времени выполнения в графике

Question

Я использую Graph в первый раз, и для этого я взял this проблему из SPOJ.

С помощью geeksforgeeks, применяемый алгоритм поиска соединений, чтобы узнать, содержит ли график цикл, но я получаю ошибку времени выполнения (SIGSEGV).

Не могли бы вы помочь, почему это так?

#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

Один вопрос это в вашей main программе:

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

Вы создали единый edge. Если i больше 0, то это доступ за пределы границ.

Посмотрите, как вы создали edge в функции create:

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

Это распределение имеет одно ребро, а не несколько ребер. Учитывая то, как вы запрограммировали остальную часть вашей программы в C-подобным же образом, что вы, вероятно, хотел это:

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

Кроме того, вы должны стремиться, чтобы не использовать имена переменных односимвольные. Трудно читать код с e, v и т. Д. В качестве имен переменных-членов. Назовите эти предметы m_edge, m_vertex или что-то более наглядное.