title: karger Minimum Cut algo crashes for big input
body: <p>I try to implement the karger Minimum Cut algorithm (<a href="http://en.wikipedia.org/wiki/Karger%27s_algorithm" rel="nofollow">Karger wiki page</a>)</p>
  
  <p>So far, I have tried my algorithm on small examples (input of size 10) and it seems to work. But when I try to have a bigger input, let's say 200. It just crashes.</p>
  
  <p>To store the minimum cut data, I create a 2D array: GraphCut[SIZE_ARRAY][SIZE_ARRAY_2]
  SIZE_ARRAY = 200 in this case, but I can't find a good length for SIZE_ARRAY_2.</p>
  
  <p>Issue is, SIZE_ARRAY_2 has to be big as I modify the initial array to merge the different vertices.</p>
  
  <p>If I declare SIZE_ARRAY_2 = 200, the size won't be enough, but if i put SIZE_ARRAY_2 = 1000, the program just crashes.</p>
  
  <p>The thing is, I have to execute the algorithm 100000 times.</p>
  
  <p>Here is parts of the code:</p>
  
  <pre><code>#define ARRAY_SIZE 200
  #define ARRAY_SIZE_2 200
  
  int main()
  {
      int minCut,minMinCut;
  
      for (int k = 0; k &lt; ARRAY_SIZE * ARRAY_SIZE * 4;k++) {
          minCut = kargerMinCut(k);
          if (k == 0)
              minMinCut = minCut;
          else if (minMinCut &gt; minCut)
              minMinCut = minCut;
      }
      printf("\n minMinCut = %d\n", minMinCut);
  
      return 0;
  }
  
  int kargerMinCut(int k) {
  // 1st dimension: each different node
  // 2nd dimension: vertices
      long graphCut[ARRAY_SIZE + 1][ARRAY_SIZE_2] = {0};
      populateIntegerArray(graphCut); // import data from a file
  
      int nodeToMain[ARRAY_SIZE + 1];
      int sizeOfMainNode, indexToMerge,initialRand,i,j,m,nodeToMerge,nodeRemaining = ARRAY_SIZE;
      for (m = 0;m&lt;ARRAY_SIZE + 1;m++) // initialization of nodeToMain
          nodeToMain[m] = m;
  
      while (nodeRemaining &gt; 2) {
  i = 0;
          j = 0;
          srand(time(NULL) + nodeRemaining);// initialise rand
          initialRand = nodeToMain[rand()%(ARRAY_SIZE) + 1]; // pick a random initial node, but not a merged one
          sizeOfMainNode = sizeOfArray(graphCut[initialRand]); // size of the initial node
  
          srand(time(NULL) + k); // initialise rand
          indexToMerge = rand()%sizeOfMainNode;// pick another random node in the linked nodes (its index to be precise)
          nodeToMerge = nodeToMain[graphCut[initialRand][indexToMerge]];
  
          for (m = 0;m&lt;ARRAY_SIZE + 1;m++)  // update the nodeToMain array, initialRand is now the main node for nodeToMerge
              if (nodeToMain[m] == nodeToMerge)
                  nodeToMain[m] = initialRand;
  
          // remove the nodeToMerge numbers from the graphCut[initialRand] (as they are going to be merged)
          while(graphCut[initialRand][j] &gt; 0 &amp;&amp; j &lt; sizeOfMainNode) {
              if (initialRand == nodeToMain[graphCut[initialRand][j]]) {
                  // if this is the last element, do nothing
                  while(nodeToMain[graphCut[initialRand][sizeOfMainNode - 1]] == initialRand &amp;&amp; j &lt; sizeOfMainNode - 1) {
                      graphCut[initialRand][sizeOfMainNode - 1] = 0;
                      sizeOfMainNode--;
                  }
                  graphCut[initialRand][j] = nodeToMain[graphCut[initialRand][sizeOfMainNode - 1]];
                  graphCut[initialRand][sizeOfMainNode - 1] = 0;
                  sizeOfMainNode--;
              }
              j++;
          }
  
          i = 0;
          while (graphCut[nodeToMerge][i] &gt; 0 &amp;&amp; sizeOfMainNode &lt; ARRAY_SIZE_2 &amp;&amp; i &lt; ARRAY_SIZE_2) { // add each vextex of the nodeTomerge to the merged nodes
              if (nodeToMain[graphCut[nodeToMerge][i]] != initialRand) {
                  graphCut[initialRand][sizeOfMainNode] = nodeToMain[graphCut[nodeToMerge][i]];
                  sizeOfMainNode++;
              }
              i++;
          }
  
          nodeRemaining--;
      }
  
      return sizeOfArray(graphCut[nodeToMain[1]]);
  }
  </code></pre>
  
  <p>I'm sure that the code is not really clean, maybe even really bad (beginner in C). So i Welcome any other advice.</p>
  
  <p>The errors I get with the debugger seems really random.
  Error is: </p>
  
  <blockquote>
    <p>Impossible to divide by 0</p>
  </blockquote>
  
  <p>it stops in time64.c at line 62</p>
  
  <pre><code>tim = (__time64_t)((nt_time.ft_scalar - EPOCH_BIAS) / 10000000i64);
  </code></pre>