#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAX_VERTICES 10000
#define MAX_EDGES 5000000 

#define HEAP_EMPTY(n) (!n)
#define LINE_SIZE  100
#define HEAP_FULL(n) (n == MAX_EDGES)


typedef struct {
  int weight;
  int node1;
  int node2;
} element;

int n_heap = 0;

element min_heap[MAX_EDGES];
int parent_array[MAX_VERTICES];

element delete_min_heap(int *n) {
  /* delete element with the highest key from the heap */
  int parent, child;
  element item, temp;
  if(HEAP_EMPTY(*n)) {
    fprintf(stderr, "The heap is empty");
    exit(1);
  }
  /* save value of the element with the largest key */
  item = min_heap[1];
  /* use the last element in the heap to adjust heap */
  temp = min_heap[(*n)--];
  parent = 1;
  child = 2;
  while(child <= *n) {
    /* find the larger child of the current parent */
    if((child < *n) && (min_heap[child].weight > min_heap[child+1].weight)) child++;
    if(temp.weight <= min_heap[child].weight) break;
    /* move to the next lower level */
    min_heap[parent] = min_heap[child];
    parent = child;
    child *= 2;
  }
  min_heap[parent] = temp;

  return item;
}

void insert_min_heap(element item, int *n) {

  int i;
  if(HEAP_FULL(*n)) {
    fprintf(stderr, "The heap is full.\n");
    exit(1);
  }
  i = ++(*n);
  while((i != 1) && (item.weight < min_heap[i/2].weight)) {
    min_heap[i] = min_heap[i/2];
    i /= 2;
  }
  min_heap[i] = item;
}

int simpleFind(int i) {
    for( ; parent_array[i] >= 0; i = parent_array[i])
        ;
    return i;

}

void weightedUnion(int i, int j) {
    int temp = parent_array[i] + parent_array[j];
    if(parent_array[i] > parent_array[j]) {
        parent_array[i] = j;
        parent_array[j] = temp;
    } else {
        parent_array[j] = i;
        parent_array[i] = temp;
    }

}

void main(int argc, char **argv) {  //argc = argument 개수 argv argument list

    //if(argc != 2) {
      //printf("No input file is given or Two many input files are given.\n");

      //exit(0);
    //}
    clock_t start = clock();
    FILE *fp1 = fopen("input_large.txt", "r"); //replace to argv[1]
    if(fp1 == NULL) {
        printf("The input file does not exist.\n");
        exit(0);
    }

    char *command_line;
    char buffer[LINE_SIZE];
    int cost;
    int n_connected;
    start = clock();
    int line_num= 0;
    int num_edges;
    int num_vertices;


    while (!feof(fp1)) {  //한줄 씩 입력받기
        element edge;
        command_line = fgets(buffer, sizeof(buffer), fp1);
        if(line_num == 0) {num_vertices = atoi(command_line);}
        else if(line_num == 1) {num_edges = atoi(command_line);}
        else {
            int vertex_from = atoi(strtok(command_line, " "));
            int vertex_to = atoi(strtok(NULL, " "));
            int weigth = atoi(strtok(NULL, " "));

            edge.node1 = vertex_from;
            edge.node2 = vertex_to;
            edge.weight = weigth;

            insert_min_heap(edge, &n_heap);

        }
        line_num++;
  }
  fclose(fp1);

  int i = 0;
  for(i = 0; i< num_vertices; i++) { parent_array[i]=-1;}
  element edge = delete_min_heap(&n_heap);


  int j = 0;
  cost = 0;
  n_connected =0;

  while((n_heap >= 0) && (n_connected != num_vertices)) {
    printf("%d %d\n", n_connected, n_heap); 연결된 vertices와 남은 힙 원소 개수 
    int node1 = edge.node1;
    int node2 = edge.node2;
    if(j == 0)  {
      weightedUnion(node1, node2);
      cost += edge.weight;
      //printf("%d %d %d\n",node1, node2, edge.weight);
      n_connected += 2;
      j++;
    }
    else if ( simpleFind(node1) != simpleFind(node2)) {
      weightedUnion(node1, node2);
      cost += edge.weight;
      //printf("%d %d %d\n",node1, node2, edge.weight);
      n_connected++;
    }
    edge = delete_min_heap(&n_heap);

  }

  printf("END\n");
  printf("COST%d\n", cost);
  printf("num vertices %d connected %d\n", num_vertices, n_connected);
  if(n_connected < num_vertices) printf("DISCONNECTED\n");
  if(n_connected == num_vertices) printf("CONNECTED\n");



  clock_t end = clock();
  double time_spent = (double)(end - start) / CLOCKS_PER_SEC;
  printf("output written to hw3_result.txt\n");
  printf("running time :%lf\n", time_spent);
}


실행결과
....
1339 4998660
1340 4998659
1341 4998658
1342 4998657
1343 4998656
1344 4998655
1345 4998

...
1657 4998343
1658 4998342
1659 4998341
1660 4998340
1661 49까지 출력
힙의 사이즈가 클 경우는

인풋 파일이 작은 경우에는 문제없이 코스트와 잘 나오지만 파일이 500000개의 Edges를 다뤄야하는데 이 경우에 이렇게 exited with code=3221225477 in 2.043 seconds의 메세지를 보내고 멈추는데 도데체 어디서 이러는지 모르겠어요....