\section{kruskal.cpp}

<<kruskal.cpp>>=
#include <iostream.h>
#include "wGraph.H"
#include "heap.H"   // lo heap di Lorenzo Dematte 

void usageSyntaxHelp(int argc, char **argv);

struct elem {
  int father;
  int card;
};

class setUnion {
  int n;    // cardinality of the ground set.
  elem * eqClass;

 public:
  setUnion(int n) {
    eqClass = new elem[n+1];
    for(int i = 1; i <= n; i++) {
      eqClass[i].father = i;
      eqClass[i].card = 1;
    }
  }
  ~setUnion() { delete eqClass; }
  void Union(int i, int j) {
    if(eqClass[j].card < eqClass[i].card) {
      int swap = i;
      i = j;
      j = swap;
    }
    eqClass[i].father = j;
    eqClass[j].card = eqClass [j].card + eqClass [i].card ;
    eqClass[i].card = 0;
  }
  int find(int i) {
    while(eqClass[i].card == 0)  i = eqClass[i].father;
    return i;
  }
};

struct edge {
public:
  int node_A;
  int node_B;
  int weight;
};

inline bool less(const edge a, const edge b) {
  return (a.weight < b.weight);
}

int main(int argc, char **argv) {
  usageSyntaxHelp(argc, argv);
   
  Graph* G = new Graph(DIMACS, argv[1]);

  heap<edge> HeapOfEdges;

  for(int v = G->n(); v; v--)
    for(int nei = G->first_neighbor(v);
        nei; nei = G->next_neighbor())
      if(nei > v) {
        edge e;
        e.node_A = v;
        e.node_B = nei;
        e.weight = G->weight(v,nei);
        HeapOfEdges.insert(e);
      }
  
  setUnion components(G->n());

  int cost = 0;
  while (!HeapOfEdges.is_empty()) {
    edge e = HeapOfEdges.min();
    HeapOfEdges.del_min();
    int component_A = components.find(e.node_A);
    int component_B = components.find(e.node_B);
    if(component_A != component_B) {
      cost += e.weight;
      cout << "arco (" << e.node_A << "," << e.node_B << ")" << endl;
      components.Union(component_A, component_B);
    }
  }

  delete G;
  exit(0); 
}


void usageSyntaxHelp(int argc, char **argv) {
   if(argc != 2)  {

      exit(1);
   }
}
@