kruskal

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

#define NMAX 100
#define MMAX 9900

typedef struct edge {
          int u, v;
          int c;
        } EDGE;

EDGE e[MMAX / 2];
EDGE tree[NMAX - 1];
int last;
int tata[NMAX + 1];


int cmp(const void* a, const void* b) {
  EDGE* pa = (EDGE*)a;
  EDGE* pb = (EDGE*)b;

  if (pa->c == pb->c) {
    if (pa->u == pb->u) {
      return pa->v - pb->v;
    } else {
        return pa->u - pb->u;
    }
  } else {
      return pa->c - pb->c;
  }
}

int find(int v) {
  int u, r;

  u = v;
  while (tata[u] > 0) {
    u = tata[u];
  }

  r = u;
  u = v;
  while (tata[u] > 0) {
    v = tata[u];
    tata[u] = r;
    u = v;
  }

  return r;
}

void join(int ra, int rb) {
  if (tata[ra] < tata[rb]) {
    tata[ra] += tata[rb];
    tata[rb] = ra;
  } else {
      tata[rb] += tata[ra];
      tata[ra] = rb;
  }
}

int kruskal(int n, int m) {
  int i, ra, rb, found;
  int cost = 0;

  for (i = 1; i<= n; i++) {
    tata[i] = -1;
  }

  last = 0;
  i = 0;
  while ((i < m) && (last < n - 1)) {
    found = 0;
    while ((i < m) && !found) {
      ra = find(e[i].u);
      rb = find(e[i].v);

      if (ra != rb) {
        join(ra, rb);

        tree[last++] = e[i];
        cost += e[i].c;
        found = 1;
      }
      i++;
    }
  }

  return cost;
}


int main() {
  FILE *fin, *fout;
  int n, m, i, aux, cost;

  fin = fopen("kruskal.in", "r");
  fout = fopen("kruskal.out", "w");

  fscanf(fin, "%d %d", &n, &m);

  for (i = 0; i < m; i++) {
    fscanf(fin, "%d %d %d", &e[i].u, &e[i].v, &e[i].c);

    if (e[i].u > e[i].v) {
      aux = e[i].u; e[i].u = e[i].v; e[i].v = aux;
    }
  }

  qsort(e, m, sizeof(EDGE), cmp);

  cost = kruskal(n, m);

  fprintf(fout, "%d\n", cost);
  for (i = 0; i < last; i++) {
    fprintf(fout, "%d %d\n", tree[i].u, tree[i].v);
  }

  fclose(fin);
  fclose(fout);

  return 0;
}