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

typedef struct arete
{
  int extr1, extr2;
  float poids;
}Arete;

int ordre, taille;

Arete * SaisirGraphe(void);
void TrierGraphe(Arete *);
Arete * ConstruireArbre(Arete *);
void AfficherSauverArbre(Arete *);

void main()
{
  Arete * graphe, * arbre;
  
  graphe = SaisirGraphe();
  TrierGraphe(graphe);
  arbre=ConstruireArbre(graphe);
  AfficherSauverArbre(arbre);  
}

Arete * SaisirGraphe()
{
  FILE * fichier;
  char nom[20];
  int i;
  Arete * LeGraphe;
  
  printf("Quel est le nom du fichier d'entrée ?\n");
  gets(nom);
  fichier=fopen(nom,"r");
  if (fichier==NULL)
    {
      printf("ce fichier n'esiste pas");
      exit(1);
    }
  fscanf(fichier,"%d",&ordre); 
  fscanf(fichier,"%d",&taille);
  LeGraphe = (Arete *) malloc(taille*sizeof(Arete));
  for (i=0;i<taille;i++)
    fscanf(fichier,"%d%d%f",&LeGraphe[i].extr1,
	   &LeGraphe[i].extr2,&	LeGraphe[i].poids);
  return LeGraphe;
}

void TrierGraphe(Arete * graphe)
{
  int i,j;
  Arete cle;
  
  for (i=1;i<taille;i++)
    {
      cle=graphe[i];
      for (j=i-1;((j>=0)&&(cle.poids<graphe[j].poids));j--)
	graphe[j+1]=graphe[j];
      graphe[j+1]=cle;
    }
}

Arete * ConstruireArbre(Arete * UnGraphe)
{
  int * NumComp;
  int sommet, num1, num2;
  int IndiceGraphe=0, IndiceArbre;
  Arete * LArbre;
  
  NumComp=(int *) malloc(ordre*sizeof(int));
  for (sommet=0;sommet<ordre;sommet++) NumComp[sommet]=sommet;
  LArbre=(Arete *) malloc((ordre-1)*sizeof(Arete));
  for (IndiceArbre=0;IndiceArbre<ordre-1;IndiceArbre++)
    {
      while ((IndiceGraphe<taille)&&
	     (NumComp[UnGraphe[IndiceGraphe].extr1]
	      ==NumComp[UnGraphe[IndiceGraphe].extr2]))
	IndiceGraphe++;
      if (IndiceGraphe==taille)
	{
	  printf("Le graphe n'est pas connexe\n");
	  exit(1);
	}
      LArbre[IndiceArbre]=UnGraphe[IndiceGraphe];
      num1=NumComp[UnGraphe[IndiceGraphe].extr1]; 
      num2=NumComp[UnGraphe[IndiceGraphe].extr2];
      for (sommet=0;sommet<ordre;sommet++)
	if (NumComp[sommet]==num2) NumComp[sommet]=num1;
    }
  return LArbre;
}

void AfficherSauverArbre(Arete * UnArbre)
{
  int i;
  FILE * fichier;
  char nom[20];
  
  printf("Voici les arêtes de l'arbre couvrant de poids minimum :\n");
  for (i=0;i<ordre-1;i++)
    printf("%d %d\n", UnArbre[i].extr1,UnArbre[i].extr2);
  printf("Quel est le nom du fichier de sortie ? ");
  gets(nom);
  fichier=fopen(nom,"w");
  for (i=0;i<ordre-1;i++)
    fprintf(fichier,"%d %d\n", UnArbre[i].extr1,UnArbre[i].extr2);
  fclose(fichier);
}