Union-Find Algorithm (Finding Cycle) Without Using Malloc

[hixtus]

Hello!

I've been advised that using malloc in a c++ program shouldn't be done. How can I convert this to a non-malloc code? Thank you!

https://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/

[zapshe]

Why shouldn't you use them? You could always try to replacing them with "new".

Check this out: https://www.includehelp.com/cpp-tutorial/difference-between-new-and-malloc.aspx

[hixtus]

Thanks so much! I used new instead and the segmentation fault problem is now gone. However, since I'm aiming for a malloc-free code, could you please help me convert this bit of code using new? Thanks!

int parent = (int) malloc( graph->V * sizeof(int) );

[keskiverto]

That code looks like plain C rather than C++.


Step 1 is to understand why the algorithm uses dynamic memory allocation. What does the algorithm(s) do?

Step 2 is to know what options does the C++ have for such tasks.

int V = 3, E = 3; 
struct Graph* graph = createGraph(V, E); 

That is C. A function creates an object.

C++ structs do have constructors to create the object:

int V = 3, E = 3;
Graph graph( V, E );

That, however, is suspicious. I can claim that the graph has 1 vertex and 7 edges, and when I fill data for those edges, enter 13 unique edges. 1 != 13. My lies won't be caught soon enough.

But I digress. Lets make believe. Convert the createGraph() into constructor:

struct Graph 
{
  Graph(int V, int E)
  : V(V), edge(E) // member initializer list syntax
  {
  }

  int V; 
  std::vector<Edge> edge; 
}; 

Can it be that short?

The struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph) );
is unnecessary, because the main can have Graph variable with automatic storage duration.

The graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );
reveals that Graph.edge is practically a dynamic array with E elements.
Constructor of std::vector does that.
Vectors edge.size() gives us the E, if we need it; no need for redundant member.


Likewise, the

struct subset *subsets = 
        (struct subset*) malloc( V * sizeof(struct subset) ); 

is clearly an array of V elements. std::vector is fine for that too.