title: segmentation fault in malloc
body: <p>I have a written the following program and every time I try to run it I get a segmentation fault. I think the problem is at the malloc of the array subsets on line 149. I tried to debug it with gdb but it says that there is a problem in function find which doesn't make any sense at all. If somebody ever had a similar problem plz help. Thanks a lot. </p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;string.h&gt;
  #include &lt;math.h&gt;
  #include &lt;inttypes.h&gt;
  
  long int N;
  
  // a structure to represent a weighted edge in graph
  struct Edge
  {
      long int src, dest ;
      long int weight;
   };
  
   // a structure to represent a connected, undirected and weighted graph
   struct Graph
   {
   struct Edge* edge;
    };
  
  
    // A structure to represent a subset for union-find
    struct subset
    {
          long int parent;
          long int rank;
          long long int vertex;
     };
  
  
      // A utility function to find set of an element i
      long int find(struct subset subsets[], long int i)
      {
          // find the root and make root as parent of i (path compression)
         if (subsets[i].parent != i)
         subsets[i].parent = find(subsets, subsets[i].parent);
  
         return subsets[i].parent;
       } 
  
  
       // Union of two sets of x and y
       // (uses union by rank)
       void Union(struct subset subsets[],long int x,long int y)
       {
          long int xroot = find(subsets, x);
          long int yroot = find(subsets, y);
              // Attach smaller rank tree under root of high rank tree
          // (Union by Rank)
          if (subsets[xroot].rank &lt; subsets[yroot].rank){
               subsets[xroot].parent = yroot;
               subsets[yroot].vertex += subsets[xroot].vertex;
          }
          else if (subsets[xroot].rank &gt; subsets[yroot].rank){
               subsets[yroot].parent = xroot;
               subsets[xroot].vertex += subsets[yroot].vertex;
          }
          // If ranks are same, then make one as root and increment
          // its rank by one
          else
          {
          subsets[yroot].parent = xroot;
          subsets[xroot].rank++;
              subsets[xroot].vertex += subsets[yroot].vertex;
          }
         }
  
       // Compare two edges according to their weights.
       // Used in qsort() for sorting an array of edges
       int comp(const void* a, const void* b)
       {
          struct Edge* a1 = (struct Edge*)a;
          struct Edge* b1 = (struct Edge*)b;
          return (a1-&gt;weight - b1-&gt;weight);
        }
  
  
  
  
        int main(int argc, char *argv[])
        {
          int j;
          long int i;
          long int n1, n2, w;
          long long int sum=0;
          FILE *f = fopen(argv[1], "r");
  
          if (!f) {
              exit(EXIT_FAILURE);
          }
          fscanf(f, "%ld", &amp;N);
  
          struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph) );
  
          graph-&gt;edge = (struct Edge*) malloc( N * sizeof( struct Edge ) );
          for (i = 0; i &lt; N-1; i++) {
              fscanf(f, "%ld", &amp;n1);
              fscanf(f, "%ld", &amp;n2);
              fscanf(f, "%ld", &amp;w);
  
              graph-&gt;edge[i].src = n1;
              graph-&gt;edge[i].dest = n2;
              graph-&gt;edge[i].weight = w;
          }
  
          long int x,y;
          struct Edge next_edge ;
  
          qsort(graph-&gt;edge, N-1, sizeof(graph-&gt;edge[0]), comp);
  
              /*
          for (i = 0; i &lt; N -1 ; i++)
          {
              printf("%ld\t %ld\t %ld\n", graph-&gt;edge[i].src, graph-&gt;edge[i].dest,             graph-&gt;edge[i].weight); 
          }
           */
          // Allocate memory for creating V subsets
          struct subset *subsets = (struct subset*) malloc( N * sizeof(struct subset) );
          // Create V subsets with single elements
          for (j = 0 ; j &lt; N ; j++)
          {
                  subsets[j].parent = 0;
              subsets[j].rank = 0;
              subsets[j].vertex = 1 ; 
          }
  
          i = 0; 
          while (i &lt; N-1)
          {
              next_edge = graph-&gt;edge[i--];
              x = find(subsets, next_edge.src);
              y = find(subsets, next_edge.dest);
              if (x != y){
                        sum += graph-&gt;edge[i].weight + ( ( graph-&gt;edge[i].weight +1 ) * (subsets[x].vertex*subsets[y].vertex-1));
                  Union(subsets, x, y);
              }
          }
  
          printf("%lld\n", sum);
  
          return 0 ;
         } 
  </code></pre>
  
  <p>P.S. The purpose of the program is, given an MST, to calculate the weight of a full tree in a way that the given MST is its only MST. </p>