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




//----------------------------------------------Structure  Kruskal ------------------------------------------------------
// Structures adaptées à partir de votre code
typedef struct arete {
    int sommet1;
    int sommet2;
    int poids;
} Arete;

typedef struct graphe {
    int nb_sommets;        // Nombre total de sommets dans le graphe.
    int nb_aretes;         // Nombre total d'arêtes dans le graphe.
    Arete* liste_aretes;   // Tableau d'arêtes.
} Graphe;

typedef struct noeudListe {
    Arete arete;
    struct noeudListe* successeur;
} NoeudListe;

typedef struct listeAretes {
    NoeudListe* tete;
} ListeAretes;



//----------------------------------------------Déclaration fonctions Kruskal ------------------------------------------------------
void Cree_graphe_oriente_a_partir_de_fichier(Graphe* G, const char* nomFichierGraphe);
int kruskal(Graphe* G, ListeAretes* foret);
void fusion(Arete* tab, int deb, int fin1, int fin);
void tri_fusion(Arete* tab, int deb, int fin);

//----------------------------------------------Kruskal ------------------------------------------------------

void Cree_graphe_oriente_a_partir_de_fichier_(Graphe* G, const char* nomFichierGraphe) {
    FILE *fichier = fopen(nomFichierGraphe, "r"); // Ouvre le fichier contenant les données du graphe en lecture.

    if (fichier != NULL) // Si le fichier a été ouvert avec succès...
    { 
        int nb_sommets, nb_aretes, sommet1, sommet2, poids;
        fscanf(fichier, "%d %d", &nb_sommets, &nb_aretes); // Lit le nombre total de sommets et d'arêtes du graphe.

        G->nb_sommets = nb_sommets; // Stocke le nombre de sommets dans la structure Graphe.
        G->nb_aretes = nb_aretes; // Stocke le nombre d'arêtes dans la structure Graphe.
        G->liste_aretes = (Arete*) malloc(nb_aretes * sizeof(Arete)); // Alloue de l'espace pour le tableau d'arêtes.

        for (int i = 0; i < nb_aretes; i++) 
        {
            fscanf(fichier, "%d %d %d", &sommet1, &sommet2, &poids); // Lit les informations de chaque arête: sommet de départ, d'arrivée et poids.
            
            // Stocke les informations dans le tableau d'arêtes
            G->liste_aretes[i].sommet1 = sommet1;
            G->liste_aretes[i].sommet2 = sommet2;
            G->liste_aretes[i].poids = poids;
        }
    } else {
        printf("Le fichier n'a pas été trouvé.\n"); // Affiche un message d'erreur si le fichier ne peut pas être ouvert.
    }

    if (fichier) fclose(fichier); // Ferme le fichier une fois le traitement terminé.
}

// Fonction de tri des arêtes par poids - à implémenter
void trierAretes(Arete* aretes, int nb_aretes) {
    // Utiliser un algorithme de tri, par exemple tri par fusion ou quicksort,
    // pour trier les arêtes par leur poids.
}

// Algorithme de Kruskal adapté



int kruskal(Graphe* G, ListeAretes* foret) {
    int* couleurs = (int*)malloc(G->nb_sommets * sizeof(int));
    int poidsTotal = 0;

    for (int i = 0; i < G->nb_sommets; i++) {
        couleurs[i] = i;
    }

    // Utilisation de tri_fusion au lieu de trierAretes
    tri_fusion(G->liste_aretes, 0, G->nb_aretes - 1);

    for (int i = 0; i < G->nb_aretes; i++) {
        int sommet1 = G->liste_aretes[i].sommet1;
        int sommet2 = G->liste_aretes[i].sommet2;
        int poids = G->liste_aretes[i].poids;

        if (couleurs[sommet1] != couleurs[sommet2]) {
            NoeudListe* noeud = (NoeudListe*)malloc(sizeof(NoeudListe));
            noeud->arete = G->liste_aretes[i];
            noeud->successeur = foret->tete;
            foret->tete = noeud;
            poidsTotal += poids;

            int nouvelleCouleur = couleurs[sommet1];
            for (int u = 0; u < G->nb_sommets; u++) {
                if (couleurs[u] == couleurs[sommet2]) {
                    couleurs[u] = nouvelleCouleur;
                }
            }
        }
    }

    free(couleurs);
    return poidsTotal;
}


//---------------------------------------------- Tri fusion kruskal ------------------------------------------------------

void fusion(Arete* tab, int deb, int fin1, int fin) {
    int taille = fin - deb + 1;
    Arete* temp = (Arete*)malloc(taille * sizeof(Arete));
    int i1 = deb, i2 = fin1 + 1, it = 0;

    while (i1 <= fin1 || i2 <= fin) {
        if (i2 > fin || (i1 <= fin1 && tab[i1].poids <= tab[i2].poids)) {
            temp[it++] = tab[i1++];
        } else {
            temp[it++] = tab[i2++];
        }
    }

    for (int i = 0; i < taille; i++) {
        tab[deb + i] = temp[i];
    }

    free(temp);
}

void tri_fusion(Arete* tab, int deb, int fin) {
    if (deb < fin) {
        int moitie = (deb + fin) / 2;
        tri_fusion(tab, deb, moitie);
        tri_fusion(tab, moitie + 1, fin);
        fusion(tab, deb, moitie, fin);
    }
}









int main() {
    Graphe G;
    ListeAretes foret = {NULL};

    // Exemple de création d'un graphe simple (remplacez ceci par la lecture d'un fichier si nécessaire)
    G.nb_sommets = 4; // Exemple avec 4 sommets
    G.nb_aretes = 5; // Exemple avec 5 arêtes
    G.liste_aretes = (Arete*)malloc(G.nb_aretes * sizeof(Arete));

    // Ajoutons quelques arêtes (sommet1, sommet2, poids)
    G.liste_aretes[0] = (Arete){0, 1, 10};
    G.liste_aretes[1] = (Arete){0, 2, 6};
    G.liste_aretes[2] = (Arete){0, 3, 5};
    G.liste_aretes[3] = (Arete){1, 3, 15};
    G.liste_aretes[4] = (Arete){2, 3, 4};

    // Appliquer l'algorithme de Kruskal
    int poidsTotal = kruskal(&G, &foret);

    printf("Poids total de la forêt couvrante minimale : %d\n", poidsTotal);

    // Nettoyage
    free(G.liste_aretes);
    while (foret.tete != NULL) {
        NoeudListe* tmp = foret.tete;
        foret.tete = foret.tete->successeur;
        free(tmp);
    }

    return 0;
}